Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The algorithm here which computes the exponent $b$ given a base $a$, and given $n$ = $a$^$b$, appears no better to me than simply counting the number of times we divide $n$ through by the base $a$ until the quotient is less than $a$ and outputting that result, which will be even less work since we compute the largest power of $a$ greater than $n$ in the first step anyway.

Yet the author discusses it at some length, and provides computer code for it. Am I missing something about this that makes it elegant? I admit it is cool, but not particularly efficient or elegant.

share|improve this question
1  
I guess it actually does less work than dividing through by $a$ $b$-times since it computes not powers of $a$ but an 'exponential Fibonacci' in the first step. Maybe this makes it better. –  Cris Stringfellow Feb 13 '13 at 13:36
    
But it doesn't appear to provide a significant advantage over the binary equivalent, which is also constant storage and logarithmic in $b$. One benefit of Fibonacci is fewer $1$s in the representation, but it comes at a higher cost of finding the first bit. –  Erick Wong Feb 13 '13 at 14:44
2  
A funny side note is that the decomposition of 95, that the author gives in the comments, is wrong, namely 95 = 65 + 21 + 8 + 1. But 65 is no Fibonacci number; it should be 95=89+5+1. –  Elmar Zander Feb 13 '13 at 15:41
    
The proof of the existence and uniqness of the decomposition is also pretty bloated. If $F(k)$ is the largest Fibonacci number smaller $n$, then $n-F(k)<F(k-1)$ follows immediately, because otherwise $n\geq F(k)+F(k-1)=F(k+1)$, which is a contradiction. –  Elmar Zander Feb 13 '13 at 15:47
    
@ElmarZander haha. yes! on all points. –  Cris Stringfellow Feb 13 '13 at 15:54
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.