## Search found 527 matches

Thu May 25, 2017 2:42 pm UTC
Forum: Mathematics
Topic: Interesting question regarding Fermat nested radicals
Replies: 9
Views: 4134

### Re: Interesting question regarding Fermat nested radicals

here's the corresponding OEIS page and it provides a an alternate equivalent formula which looks much easier to work with and also a efficient algorithm

https://oeis.org/A273580

Thu May 25, 2017 6:38 am UTC
Forum: Mathematics
Topic: properties of a certain game
Replies: 2
Views: 2542

### properties of a certain game

this is a two player, zero-sum game. the state is 2 vectors and two scalars (one vector and scalar per player). call the vectors x and y and the scalars p and q respectively. x and y have some fixed dimension k. (and if it makes things easier, feel free to let k be infinite) player 1 wins if p > 0 a...
Sat May 20, 2017 3:16 pm UTC
Forum: Mathematics
Topic: Any machine learning folks on this forum?
Replies: 3
Views: 2880

### Re: Any machine learning folks on this forum?

linear regression models are pretty fundamental and widely used -- in fact, my school has an entire semester long course on various forms of linear regression. and i would bet that in terms of "number of times applied", this would be the winner two other good ones are decision trees + thei...
Mon May 01, 2017 6:41 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

(y, y) is a pair, which is encoded as string x, so x = <(y,y)> which i've written with a bit of notation abuse as x = <y,y>
Mon May 01, 2017 5:30 pm UTC
Forum: Coding
Topic: Basic Question Involving Functions (Python)
Replies: 18
Views: 12280

### Re: Basic Question Involving Functions (Python)

if the function name is fn, you can run the command help(fn) to print out instructions and information on what inputs it takes. google is also another resource
Mon May 01, 2017 5:21 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

try to think of them as physical machines instead of programs. a machine takes in a string as an input, and spits out yes, no, or loops forever now if you try to put one machine D inside another machine M, that's not possible, because machines can only take string as input. so what we do instead is ...
Mon May 01, 2017 5:16 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

yes, we write D to represent the program (program-use), and <D> to refer to the "string-use" (aka encoded) version of D
Mon May 01, 2017 5:06 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

yes, that makes sense. it will help to understand the idea of encoding something often, we want programs to take other mathematical objects as input, such as pairs of numbers, lists of pairs of numbres, or even other computer programs however, formally, computer programs can only take strings as inp...
Mon May 01, 2017 4:59 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

no, i don't think so. but there are not that many programs and arguments. we have M, the halting problem solving program, which takes the bare minimum it needs! it only takes the program and the input you want to test. then we have D, the program which we are designing to mess up M. D only takes a s...
Mon May 01, 2017 4:54 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

it's not super important, but under the turing model of computation, turing machines (aka computer programs) take exactly one string as an input. of course, if you want to feed a machine two inputs, you can just combine the two inputs and put a delimiter between them. for example, you might feed two...
Mon May 01, 2017 4:49 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

what i gave is a proof-by-contradiction type proof. just try to follow all the inputs and explain where you get stuck -- there are only two machines, each of which takes one input (well M takes one pair...)
Mon May 01, 2017 4:46 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

What I'd like to make sense of now is the program-within-a-program paradox Here's a pretty standard proof I think. I'll use <> angle brackets to denode encoding. First we suppose that we have some program M, such that M(x) tells us if the program and input pair encoded by x will halt. In other word...
Mon May 01, 2017 4:32 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

well suppose you wrote a program to multiply two numbers. it doesn't make much sense to talk about whether the program halts, because it won't really do anything unless you give it some input (the numbers to be multiplied). even the empty string is a valid input, of course formally, the halting prob...
Mon May 01, 2017 4:27 pm UTC
Forum: Mathematics
Topic: Halting Problem
Replies: 208
Views: 46232

### Re: Halting Problem

That is a great explanation, thank you. What I'm stuck on is the standard explanation in which one assumes that there's a program that can tell you whether any particular program fed into it will halt (or not halt). That's where I get hung up. the proof usually follows this logic: suppose it is pos...
Mon May 01, 2017 2:56 am UTC
Forum: Coding
Topic: Coding: Fleeting Thoughts
Replies: 9990
Views: 2006396

### Re: Coding: Fleeting Thoughts

just to eek that last bit of performance out of python, i manually inlined all my helper functions into one single monstrous blob of code. just about doubled the speed too, which is way more than i expected, but it still wasn't good enough, so i had to rewrite it in c++
Mon May 01, 2017 2:20 am UTC
Forum: Mathematics
Topic: Math/Cryptography Questions
Replies: 8
Views: 2852

### Re: Math/Cryptography Questions

no, it is possible to quickly prove that a number is prime without trying to factor it! the first (and possible only known) deterministic algorithm for doing so is the AKS primality test https://en.wikipedia.org/wiki/AKS_primality_test for some intuition, suppose i randomly generate a function f whi...
Mon May 01, 2017 2:11 am UTC
Forum: Mathematics
Topic: Math/Cryptography Questions
Replies: 8
Views: 2852

### Re: Math/Cryptography Questions

polynomial means the running time grows polynomially in the size of the prime you want to generate. for example, if the polynomial were n^2, you could guarantee testing if a 4096 bit number is prime would take not more than 4^2 = 16 times as long as testing a 1024 bit number factoring is not known t...
Mon May 01, 2017 2:02 am UTC
Forum: Mathematics
Topic: Math/Cryptography Questions
Replies: 8
Views: 2852

### Re: Math/Cryptography Questions

1. yes, it is much easier to test if a number is prime (polynomial), than it is to factor a prime (unknown if polynomial). even though factoring a prime is not known to be NP-complete, this is kind of like many other NP-complete problems, where something like finding the shortest traveling salesman ...
Sat Apr 01, 2017 4:40 pm UTC
Forum: Computer Science
Replies: 120
Views: 64293

I guess it's just convention really, since i've only ever seen log log n written as log log n
Wed Mar 29, 2017 1:57 am UTC
Forum: Mathematics
Topic: behavior of best estimator on some constructed mixture distribution
Replies: 3
Views: 2520

### Re: behavior of best estimator on some constructed mixture distribution

can you explain why the mixed distribution has some oher best estimator? is it based off of intuition or some paper?

thanks
Mon Mar 27, 2017 8:38 pm UTC
Forum: Computer Science
Replies: 120
Views: 64293

because a binary counter going from 1 to n needs at least log n bits. I'm not sure how cpp iterators are implemented, but they are probably just 64 bit datatypes, in which case do not actually solve this problem correctly for graphs with more than 2^64 vertices ive always written it as log^2 n as op...
Mon Mar 27, 2017 3:05 pm UTC
Forum: Computer Science
Replies: 120
Views: 64293

Yes, that is indeed where the extra log factor comes from. And it does work for both directed and undirected versions -- I was just mentioning at the end that in the undirected case, there is an even more efficient algorithm which runs in just log n space.
Sun Mar 26, 2017 10:12 pm UTC
Forum: Computer Science
Replies: 120
Views: 64293

i learned this algorithm for finding a path from vertices s to t in a graph in class recently: //is there a path of length at most k from s to t? loop over vertices w in V: recursively compute if there is a path from s to w with length at most ceil(k/2) recursively compute if there is a path from w ...
Thu Mar 16, 2017 7:55 pm UTC
Forum: Mathematics
Topic: behavior of best estimator on some constructed mixture distribution
Replies: 3
Views: 2520

### behavior of best estimator on some constructed mixture distribution

I'm taking a course in statistical inference. We showed in class that: 1. the best estimator for the mean of a normal distribution (and probably most common distributions?) is the sample mean 2. the best estimator for the range of a uniform distribution which goes from 0 to theta involves multiply t...
Tue Mar 07, 2017 1:39 pm UTC
Forum: Mathematics
Topic: vertex cut / graph / combinatorics problem
Replies: 5
Views: 2689

### Re: vertex cut / graph / combinatorics problem

wow, that looks like a pretty solid proof to me, thanks! for the last part, we can do it rigorously by induction clearly, the first path of the villian is at least as high as q1 in all countries then when considering the qk and vk (the villian's kth path), we know that q(k-1) <= v(k-1) then delete a...
Mon Mar 06, 2017 9:25 pm UTC
Forum: Mathematics
Topic: vertex cut / graph / combinatorics problem
Replies: 5
Views: 2689

### Re: vertex cut / graph / combinatorics problem

I'm not quite sure that works out for example, consider 3 countries and the elevation of their cities: country 1 has 10 5 4 country 2 has 9 8 3 2 country 3 has 7 6 1 then your method removes nothing, and shuts down 3 airports (either in country 1 or 3) whereas the greedy strategy removes the path 10...
Mon Mar 06, 2017 6:05 pm UTC
Forum: Mathematics
Topic: vertex cut / graph / combinatorics problem
Replies: 5
Views: 2689

### vertex cut / graph / combinatorics problem

suppose there are a bunch of countries, each containing a set of cities, and each city has an elevation (all distinct). also suppose someone on a glider wants to visit exactly one city from every country. obviously, since she's on a glider, she can only go from higher elevation to lower elevation ci...
Mon Feb 27, 2017 7:10 pm UTC
Forum: Mathematics
Topic: Help with a 9 Variable Equation
Replies: 6
Views: 2925

### Re: Help with a 9 Variable Equation

what exactly do you mean by proportion of a variable and H? is it the ratio?
Mon Feb 27, 2017 12:36 pm UTC
Forum: Mathematics
Topic: WoW: A Strange Game. The only way to win is not to play.
Replies: 7
Views: 3087

### Re: WoW: A Strange Game. The only way to win is not to play.

I would think evo algs are better than most optimization algs at dealing with highly nonconvex functions, since if an individual does take a step in the wrong direction and becomes terrible, it is immediately eliminated. plus in the vast majority of cases, deviating a strategy should result in prett...
Wed Feb 22, 2017 10:43 pm UTC
Forum: Computer Science
Topic: Why don't we use composite hashes?
Replies: 5
Views: 6948

### Re: Why don't we use composite hashes?

yes in that case, where you want to fake a certificate, definitely makes the security at least as good as before, because any algorithm which can create fake certificate for the concatenated hash also makes a fake certificate for all the component hashes
Wed Feb 22, 2017 2:06 pm UTC
Forum: Computer Science
Topic: Why don't we use composite hashes?
Replies: 5
Views: 6948

### Re: Why don't we use composite hashes?

i think it's possible that there could be some problems with this, even though it sounds pretty good in practice for example, suppose it just happened that (sha2(x) and md5(x)) xor sha1(x) = x (the first 256 bits of x, or something) [edit: just saw your bit in the post about m1 != m2, but isn't allo...
Mon Feb 20, 2017 11:13 pm UTC
Forum: Coding
Topic: Coding: Fleeting Thoughts
Replies: 9990
Views: 2006396

### Re: Coding: Fleeting Thoughts

That sounds pretty horrifying, and i'm not sure it would run faster after all the overhead. Luckily, I was dealing with prime gaps, so even though the primes themselves had to be put in int64's, the gaps were nice and small enough to fit in a float edit: hmm, so according to nvidia's cuda documentat...
Sat Feb 18, 2017 6:53 pm UTC
Forum: Coding
Topic: Coding: Fleeting Thoughts
Replies: 9990
Views: 2006396

### Re: Coding: Fleeting Thoughts

i've been playing around with brute force testing some open but obscure number theory conjectures on a high end GPU recently. the speedup is nice about 10x ... but not as much as expected. i think this is due to the relatively low int64 compute performance on a gpu compared to the float32 performanc...
Tue Jan 31, 2017 1:15 pm UTC
Forum: Mathematics
Topic: variance of a sum of iid random variables
Replies: 2
Views: 2317

### Re: variance of a sum of iid random variables

ah, nice spot, I'd somehow forgotten about those terms
Tue Jan 31, 2017 4:04 am UTC
Forum: Mathematics
Topic: variance of a sum of iid random variables
Replies: 2
Views: 2317

### variance of a sum of iid random variables

consider y_1 to y_n as i.i.d. random variables with mean u, and let X = sum 1 to n of y_i then E[X]^2 = (nu)^2 E[X^2] = E[(sum i = 1 to n of y_i)^2] = E[sum i, j from 1,1 to n,n of y_i y_j] = sum i,j from 1,1 to n,n of E[y_i y_j] (by linearity of expectation) = sum i,j from 1,1 to n,n of E[y_i] E[y_...
Sun Dec 25, 2016 11:27 pm UTC
Forum: Mathematics
Topic: chain rules matrix derivatives
Replies: 2
Views: 2006

### chain rules matrix derivatives

I have trouble with taking derivatives / gradients / jacobians of matrix expressions. I don't have any "formal education" in this area, and when I search, i can find a lot of identities, which don't help that much. My (naive) approach to finding the gradient of expressions ∇_x f(x) is 1. t...
Sat Dec 24, 2016 4:40 am UTC
Forum: Mathematics
Topic: Can't keep up with all the math behind machine learning
Replies: 3
Views: 2335

### Re: Can't keep up with all the math behind machine learning

I'm sort of in the same position as you, self-studying ML. I don't have much pedagogical knowledge, but my approach is to pick up a standard textbook (Bishop, Mitchell, or Murphy), and work my way through it. I skip through things I find boring if i want, until I have to come back to it to understan...
Fri Dec 23, 2016 5:08 am UTC
Forum: Mathematics
Topic: expected "lifespan" of a random process
Replies: 4
Views: 2181

### Re: expected "lifespan" of a random process

yeah that sounds right, i'd just realized i had misread something. well that's a really disappointing result, i was really hoping that the lifespan could be finite.
Fri Dec 23, 2016 1:19 am UTC
Forum: Mathematics
Topic: expected "lifespan" of a random process
Replies: 4
Views: 2181

### Re: expected "lifespan" of a random process

In your first equation, when you write T(n) = 1 + sum_{m=1}^{kn} B(kn,m) p^m T(m) . do you mean T(n) = 1 + sum_{m=1}^{kn} C(kn,m) (1-p)^(kn-m) p^m T(m) with C(kn,m) denoting kn choose m? I'm a bit confused by the B you use. I'm also a bit confused about how your approximation method works. I think y...
Tue Dec 20, 2016 1:38 pm UTC
Forum: Mathematics
Topic: expected "lifespan" of a random process
Replies: 4
Views: 2181

### expected "lifespan" of a random process

Suppose we have x_0 = 1 and x_i ~ Binomial(k*x_{i-1}, p), where k and p are constants. I want to find the expected value of the largest value j such that x_j > 0. How do I do this? My attempt is to have an indicator random variable, z_i to denote the event that x_i > 0. Then i simply find the sum of...