13
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice method, but I don't think you're going to be able to handle numbers up to 2147483647 in practice by adding 1 repeatedly! \$\endgroup\$ – Mitchell Spector May 2 at 2:31
  • \$\begingroup\$ @MitchellSpector Given that modern computers can already do more than 2147483637 operations in a second, I don't think this will take more than a few hours. (I'm not sure how fast is C# regex though) (update: 100000 takes 20 seconds, I underestimated the slowness of C#) \$\endgroup\$ – my pronoun is monicareinstate May 2 at 2:49
  • \$\begingroup\$ @mypronounismonicareinstate I think it would take about a week. I don't have Retina installed on my computer to try out larger inputs, but TIO computes the value for 100,000 in about 26 seconds, and the value for 200,000 in about 54 seconds. Assuming a linear running time (which probably gives an underestimate), computing the value for 2147483647 would take about 2147483647 / 200000 * 54 / 60 / 60 / 24 = 6.7 days. \$\endgroup\$ – Mitchell Spector May 2 at 3:06
  • \$\begingroup\$ @mypronounismonicareinstate The algorithm makes all the difference. The dc computation gets the answer for 2147483647 in less than a second, and I don't think dc is a particularly fast language. On the other hand, Neil's Retina solution is 29 bytes shorter than my dc solution, and this is code golf! \$\endgroup\$ – Mitchell Spector May 2 at 3:09
  • 1
    \$\begingroup\$ @Neil Absolutely! This wasn't a criticism of your answer, which is a perfect codegolf solution. I was just amused at the idea of counting to 2147483647. My dc program, as it stands, will fail at some point (even assuming unlimited resources) because the calculations won't have enough decimal places. To make it truly unlimited precision like yours, I'd need to figure out at the beginning how many decimal places are needed. Here I just put in a constant number of decimal places that works for inputs up to 2147483647, which was the requirement. \$\endgroup\$ – Mitchell Spector May 2 at 16:12
4
\$\begingroup\$

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.

Sample run on a very large Lucas number

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.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 for using macOS Preview. \$\endgroup\$ – Cloudy7 May 3 at 18:27
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ The base \$\varphi\$ expansion for 111 is 1010001010.0000100001, but your program outputs 101000101 (one digit too few before the "decimal" point, and it's missing the digits after the point). \$\endgroup\$ – Mitchell Spector May 5 at 5:33
  • \$\begingroup\$ 111 is fixed, but it looks like there are still some problems with larger numbers. 100000 gives 101010001010100000100000.1010001010000000100000001010101010101010101 but I think the answer should be 101010001010100000100000.101000101000000010000001. (I would guess that there's a round-off error affecting the floating-point arithmetic.) \$\endgroup\$ – Mitchell Spector May 6 at 17:56
  • \$\begingroup\$ @MitchellSpector yep it's the whole point of multiplying the values by 1000000 past a certain point. Like other languages PHP can't properly subtract (or even compare equal values) when one of them gets really small. (float)number_format($a-$b,3)>=0 is one way I found, particularly for $a==$b. I will review some of the settings for the fix, thanks \$\endgroup\$ – Kaddath May 7 at 8:35
0
\$\begingroup\$

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 ^
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.