http://arxiv.org/abs/1401.7718
(Submitted on 30 Jan 2014 (v1), last revised 10 Mar 2014 (this version, v2))
I'm surprised that there is no other discussion of this in an actual news publication about mathematics (I read those for my occupation, and am a member of several online groups that discuss mathematical research), so I wonder if the recycled press release submitted here is really the only interest that this paper has gathered in the mathematical community.
Arguably more famous algebraic numbers include: 0, 1, The square root of two, the square root of any integer, i, any integer, the nth root of any integer,...
Out of the list of algebraic numbers in question, zero is the most infamous.
> "In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients (or equivalently—by clearing denominators—with integer coefficients)."
I almost forgot, the set of algebraic numbers also includes complex numbers.
> Let F be a subfield of a field E. An element \alpha of E is said to be {algebraic} over F if there exist elements a_0, ..., a_n (n >= 1) of F, not all equal to 0, such that a_0 + a_1\alpha^n + ... + a_n\alpha^n = 0.
point being, even a sub-par undergrad knows how to generalize algebraic numbers using some machinery that was just beginning to be built in Ramanujan's time (and of course was completely unavailable to the man himself), and now these guys have plugged fields into something that i'd only heard of in the context of group theory and proved something useful. way to go. but at the same time, if Ramanujan saw this, i have to imagine he'd be thinking something along the lines of, "the game ain't the same." (not that it's a game.)
The nth number in Fibonacci sequence is denoted by f(n)
The golden ratio is equal to the limit of f(n)/f(n-1) as n increases without limit.
A recursive implementation of the nth number in the Fibonacci sequence in C:
unsigned long long fib(int a) {
return a>1 ? fib(a-1)+fib(a-2) : 1;
}
Time taken to execute the function fib(a) is denoted by t(a).
As n increases without limit t(n)/t(n-1) approaches the golden ratio.
In practise this should give you a rough value of the golden ratio.
The reason this happens is because the function can only increase the return value by unity, one call at a time.
f(n+2)=f(n+1)+f(n)
If you posit that this number has a solution in f(n)=a^x, you see that
a^(n+2)=a^(n+1)+a^n
Dividing by a^n, you get a^2=a+1, a simple quadratic with two roots, (1+sqrt(5))/2 and (1-sqrt(5))/2, or the golden ratio and approximately -0.618.
Because any constant multiple of the function will also solve the equation, a solution to f(n) will be some linear combination of f(n)=c1(1.618..)^n+c2(-0.618)^n, for constants c1 and c2. You calculate c1 and c2 to match your initial conditions.
As n increases, the second term tends to 0, so f(n+1)/f(n) approaches the golden ratio.
Your comment reminded me of chaos theory, small changes in initial conditions can have a radical effect upon the final outcome. In this case it seems to be the opposite.
> Because any constant multiple of the function will also solve the equation, a solution to f(n) will be some linear combination of f(n)=c1(1.618..)^n+c2(-0.618)^n, for constants c1 and c2. You calculate c1 and c2 to match your initial conditions.
Bear with me a second, I have to fish out an old geometry book...
"Geometry", Roger Fenn, Springer-Verlag 2001, page 24:
I've got it, the equation you gave is very similar to Binet's Formula:
http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
unsigned long long fib(int a) {
unsigned long long x, y, temp;
while (a > 0) {
temp = x;
x = y;
y = y + temp;
--a;
}
return y;
}
To be more precise, it is an inefficient method of calculating a Fibonacci number. Using your function, if you were to measure the execution time of fib(n), then divide it by the execution time of fib(n-1), would you get a more precise value of the Golden ratio?
> This is much faster and won't blow up your stack quite so much.
Or we could use an iterative version ... wait up your code changed to an iterative implementation. Man that's weird.
EDIT:
Your code:
unsigned long long fib(int a) {
unsigned long long x, y, temp;
while (a > 0) {
temp = x;
x = y;
y = y + temp;
--a;
}
return y;
}
This function has a name: t(a) = fib(a) (up to some fiddling with constants, depending on how you count execution 'time').
I was thinking of either time() or gettimeofday() from the standard and POSIX libraries respectively.
You are saying rational numbers are countable but irrational numbers are not countable (uncountably infinite)
This is true.
The parent is saying that algebraic numbers are countable and transcendental numbers are not countable.
The parent's statement is a level deeper and more remarkable. Another way to say this, is that "almost all" numbers are transcendental.
The parent was not suggesting that his short list of examples represented the extent of transcendental numbers: despite almost all numbers being transcendental, they are individually hard for us to define, since the set is normally defined by excluding sets of numbers that we can easily define.
To clarify: transcendental numbers are a subset/a type of irrational numbers. https://en.wikipedia.org/wiki/Transcendental_number If you take out transcendental numbers from the irrationals, those that remain are algebraic and therefore countable. You got it :)
Meta Math!
Sorry about the code change, the first version was from an old memory and the new version is what happened after I stared at it for a while :) Primitive values are automatically initialized to 0 in C. As for the ratio, it will probably just give a good approximation of 1 as a gets large! Also if you have a good square root function, you can use it to find a Fibonacci number in constant time, so your ratio will always be 1 (until the square root is too big to be computed in a single instruction).
No, they're not. Automatic variables without an initializer have an indeterminate value. See http://stackoverflow.com/questions/6212921/is-un-initialized...
From the number of downvotes, I think it was mis-parsed by several HN readers. This happens to me quite often, on many a website, but I have no inkling why.
> Sorry about the code change, the first version was from an old memory and the new version is what happened after I stared at it for a while
No worries, I thought the original slice of code that you posted was more interesting and novel, it wouldn't have occurred to me off the top of my head.
> Primitive values are automatically initialized to 0 in C.
I had to look that up, good old Stack Overflow has again furnished us with an explanation.
http://stackoverflow.com/questions/10089551/what-are-primiti...
If you use an iterative / tail-recursive version you can actually do this directly, without even the overhead of having to calculate it twice.
(I.e. define fib to return a tuple / struct / etc consisting of (fib(n), fib(n-1)).)
That has been done millions of times over the past 800 odd years. My method has no practical uses, but plenty of educational ones.
But this is untrue, is it not? Because even if you removed all of the real transcendentals, the real numbers would still be uncountable because of the irrationals.
(Edit: Or are the non-transcendental irrationals countable? I can see how that might be true?)