Devise an algorithm for writing any positive base ten integer in base φ number system.
**** φ, called the Golden Ratio is a positive real number equal to (1+√5)/2
I am withdrawing my solution because I realize I
don't know how to write numbers in a real base system
(as opposed to writing in an integer base system). E.g. what is the range of the digit in any decimal place.
Later: nope - my algorithm is correct. Here is my original post verbatim:
Call alpha "a"
Algorithm to express integer N as a real number in base a:
Call epsilon the maximum remainder allowed
Define i, the index of the number of decimal places to the left of the decimal place: i = 0,1,2,3...
and to the right of the decimal place: i=-1, -2, -3. e.g., 67.8 has 6 at i=1, 7 at i=0, and 8 at i=-1.
Define D_i as the integer digit to be written at decimal place i
1) Calculate x, the log base a of N
x = log_a N = log_10 N / log_10 a
(this follows from taking the common log of both sides of N = x^a)
Define I as the integer part of x
Initialize N_old = N
Loop with i go I, I-1, I-2, I-2 ... until |N_old| < epsilon
D_i = integer part of N_old / a^i
N_old <-- N_old - D(i) a^i
End of Loop
I discovered I actually had the answer right. I just got spooked
by the ones!
Added even later: I attempted to implement my algoritm in code, and ran into the same roundoff problems as discussed by Charlie and Larry. But I chose not to solve them because the algorithm itself is still correct. Implementing it is difficult, but that's now a computer limitation, not an algorithm problem.
Edited on January 29, 2022, 2:05 am
soln
