Base-phi converter time!

Question

The Golden Ratio Bureau is obsessed with this new thing they call base-phi. You see it and decide to code-golf, as is your natural instinct.

To be specific, base-phi is a number system like base 10, except it uses the number phi, or the golden ratio, as its base. A ones digit would be x*10^y, but in base phi 10 is replaced with phi. Base phi also uses 2 digits, 0 and 1.

Your goal is to accept input that is a base 10 positive natural number, then treat it as such and convert it to base phi.

Due to base phi being able to represent all numbers in more than one way, your program should convert input to its "minimal" representation. This is the representation with the least 1 digits. Output can have trailing characters but only if the language must output them with no circumvention.

Do not use any built-ins for base conversion. You may use a built-in for phi, but the base conversion should rely on string manipulation and other mathematical operations.

Your program must support inputs up to 2147483647, or lower, depending on your language's limit for integers.

Your program can deal with any undefined behavior as you wish.

Testing cases for accuracy can be done at this link. In case you do not wish to use the link, here are the numbers 1-15 in base phi.

1 = 1
2 = 10.01
3 = 100.01
4 = 101.01
5 = 1000.1001
6 = 1010.0001
7 = 10000.0001
8 = 10001.0001
9 = 10010.0101
10 = 10100.0101
11 = 10101.0101
12 = 100000.101001
13 = 100010.001001
14 = 100100.001001
15 = 100101.001001

The shortest program following these rules wins. Have fun.

Answer 1

Retina, 81 80 bytes

K`0.
"$+"{+`(1(\.)|(1\.(0?1)*0?)1)(00|$)
${3}0${2}11
0\.
1.
+0`0?1(\.?)1
10${1}0

Try it online! Works by repeatedly adding \$ 1 \$. Explanation:

K`0.

Start off with \$ 0. \$.

"$+"{`

Repeat the number of times given by the input.

+`(1(\.)|(1\.(0?1)*0?)1)(00|$)
${3}0${2}11

If the \$ \phi^0 \$ bit is set, use the identity \$ \phi^0 = \phi^{-1} + \phi^{-2} \$ to move bits away until there is enough room.

0\.
1.

Add \$ 1 \$.

+0`0?1(\.?)1
10${1}0

Minimise the number of bits by reversing the above identity.

Answer 2

dc, ^{107 106 110} 109 bytes

[0sD]sZ0ddsRsK?dsXZF*dkdsN-sM[lX5v1dsD+2/lN^dsY>ZlXlDlY*-sXlDdAlN^*lR+sRlKdlN+lD*-sKlN1-dsNlM!>L]dsLxlRlKk1/p

Try it online!

Or verify the test suite: the OP's test cases, 2147483647, and a very large Lucas number (over 400 trillion) which comes out neatly in base \$\varphi\$ (see screenshot below for that last test case by itself).

The program should now work for arbitrarily large numbers, restricted only by the memory capacity of the computer.

How it works:

[0sD]sZ    Macro Z, sets D to 0 when called.
0ddsRsK    Initialize R and K to 0, leaving 0 on the stack.
?dsX       Input number, store it in X,
ZF*dkdsN       store 15 times its number of decimal digits in N,
               also set that as the number of decimal places for
               computations,
-sM            and store the negative of that in M.
               M and N are bounds on the powers of phi which
               will be needed for the representation.
               Multiplying by 15 is far more than is needed:
                  For M and N, we could have multiplied by just 5,
                  because ln(10)/ln(phi) < 5.
                  We need some additional decimal places in the
                  computations to handle possible round-off errors,
                  so we conservatively multiply by 15.
[          Start a macro (which will be used as a loop).
 lX                 Push X onto the stack.
 5v1dsD+2/lN^       Set D=1.  Compute phi^N,
 dsY                   and store it in Y.
 >Z                 If phi^N > X, use macro Z to set D=0.
 lXlDlY*-sX         If D is 1, set X = X - phi^N.
 lDdAlN^*lR+sR      R += D * 10^N.
                       This places the digit D in R in the right
                       position, treating R as a number in base 10.
 lKdlN+lD*-sK       If D is 1, set K = -N.
                       (K is used as the number of "decimal"
                       places to print.)
 lN1-dsN            Set N = N-1, leaving the new value of N
                       at the top of the stack.
 lM!>L              If M <= N, call macro L recursively (in
                       other words, start another loop iteration).
]          End the macro,
dsL          save it in register L,
x            and execute it.

       Once the loop is done:
lR         Load the result R.
lKk        Set the precision (number of decimal places) to K.
1/         Divide R by 1 to convert it to the desired precision.
p          Print it.

Answer 3

Perl 5, 135 bytes

sub f{(0,1,10.01)[$_=pop]||do{$_=f($_-1);$_.=0until/\..{99}/;s/.\./$&+1/e;1while s/.?2../$&+801/e+s,0?11,100,;s,.{99}$,.$&,;/1.*1/;$&}}

Try it online!

This function is no speed monster, but it's O(n). f(1000000) returns 10100000100010010000100010001.0001000010100101000100000101 in 15 secs on my laptop.

Answer 4

PHP, 173 bytes

$p=.5+sqrt(5)/2;for($i=45,$a=$argn,$f=1;$a>=.01;){$i?:$a*=$f=1e6;$b=$p**$i*$f;if($i--==-1)$n.='.';if((float)number_format($a-$b,3)>=0){$a-=$b;$n.=1;}else$n.=$n?0:'';}echo$n;

Try it online!

It was a real pain mostly because of errors in comparisons and subtraction when values get really small, I had to find a way to circumvent them:

$p=(1+sqrt(5))/2;                       //ϕ
for($i=45,$a=$argn,$f=1;$a>=.1;){       //no need to go beyond ϕ^45 to go up to 2147483647. $a is the input, $f a factor
  $i?:$a*=$f=1e7;                       //small numbers fix: multiplying $a and factor $f by 1000000 for following test and exit condition to work (also shortens this condition)
  $b=$p**$i*$f;                         //current power of ϕ multiplied by the factor
  if($i--==-1)$n.='.';                  //decrement $i + if we get to power -1 add the dot '.'
  if((float)number_format($a-$b,3)>=0){ //second fix to be right when difference is very small
    $a-=$b;                             //subtract the current power when ok
    $n.=1;                              //adding a '1'
  }else $n.=$n?0:'';                    //or else a '0' (test $n to avoid leading zeroes)
}
echo$n;                                 //et voilà!

I think I can golf it more, we'll see later, I'm open to suggestions. Note that my version of 2147483647 is slightly different than what I saw here, but of course it's me who's right. Haven't tried other big values..

EDIT: saved 1 byte thanks to @mathjunkie and lowered the exit threshold to 0.01 for the 111 case as rightly noticed by @MitchellSpector.. no change to the score

EDIT2: changed the factor from 10000000 to 1000000 to handle another case found by @MitchellSpector, I guess I'll have to do automated tests to detect other cases :D

Answer 5

APL (Dyalog Unicode), 94 bytes

{w←{+\∘⌽⍣⍵⊢1 0}¨⍵-⍳k←2×⍵⋄s/⍨(∨\'0'≠s)∧⌽∨\'1'=⌽s←⍵(↑,'.',↓)⊃∘⍕¨⊢/b/⍨(w+.×b←(0∘⍪,1∘⍪)⍣k⍪⍬)≡¨⊂⍵0}

Try it online!

Inefficient as hell. Basically, given n as input, generate all bit patterns with n bits above and n bits below the decimal point, symbolically evaluate it as base phi (to the form a+b*phi), extract all patterns whose value is n+0*phi, pick the one that is lexicographically highest, and then trim unnecessary zeros/decimal point from both ends.

Ungolfed with comments

f←{                    ⍝ Input: ⍵←n
  v←⍵-⍳2×⍵             ⍝ Vector of n-1, n-2, ..., -n
  w←{+\∘⌽⍣⍵⊢1 0}¨v     ⍝ Reduced base-phi values (a+b×phi) of phi^v
    {          }¨v     ⍝ For each value of v,
            1 0        ⍝ Start with 1+0×phi
     +\∘⌽              ⍝ Apply "reverse then cumulative sum"
         ⍣⍵            ⍝ v times (for negative v, inverse of it |v| times)

  b←(0∘⍪,1∘⍪)⍣(2×⍵)⍪⍬  ⍝ Matrix of all possible bit patterns for 2n bits
                   ⍪⍬  ⍝ Empty matrix of 0 row, 1 column
    (0∘⍪,1∘⍪)          ⍝ Apply "horizontally concat the matrix with
                       ⍝   a 0-row prepended with the one with a 1-row"
             ⍣(2×⍵)    ⍝ 2n times

  a←⊢/b/⍨(w+.×b)≡¨⊂⍵0  ⍝ Find target bit pattern
         (w+.×b)       ⍝ Evaluate each bit pattern as base phi
                ≡¨⊂⍵0  ⍝ Compare with n+0×phi
      b/⍨              ⍝ Filter columns of b where ^ is true
    ⊢/                 ⍝ Pick the rightmost one

  s←⍵(↑,'.',↓)⊃∘⍕¨a    ⍝ Convert to string
              ⊃∘⍕¨a    ⍝ Char-ify each digit
    ⍵(↑,'.',↓)         ⍝ Insert decimal point after n chars

  s/⍨(∨\'0'≠s)∧⌽∨\'1'=⌽s  ⍝ Filter away trailing non-ones and leading zeros
               ⌽∨\'1'=⌽s  ⍝ Boolean mask to filter away trailing non-ones
              ∧           ⍝ And
     (∨\'0'≠s)            ⍝ Boolean mask to filter away leading zeros
  s/⍨                     ⍝ Filter s using ^
}