Compute phi in base x

Hi from /sci/...  There was just a short thread about the digits of pi.  I personally think that phi (golden ratio) is far more interesting and was hoping one of you gentlemen might have some code to compute arbitrary digits of phi in any base chosen by the user.  Hopefully it isn't offensive to ask that it be in C.

Since it's purely random, there's going to be some sort of image in there, eventually.  Just curious to see what the first "significant" finding is.

nigger, just use gmp

>>2
I downloaded it and am struggling through the install...  It's a lot of trouble.  I don't know exactly what I'm supposed to do with a "Makefile.am" file, but I guess I'll come to that in the docs somewhere.

I still think it would be easier just to write a little code.  Phi is basically just the square root of 5...

Ok, gmp is dildos, I have gone far enough down that rat hole.  I will search elsewhere for an algorithm.

Thanks anyway.

#include <math.h>
#include <stdlib.h>

int main(void) {
    printf("%f\n", (1 + sqrt(5))/2);
    return 0;
}

>>1
Since it's purely random, there's going to be some sort of image in there, eventually
This thread is now about disproving this statement.

>>6
Well, there's obviously "an image" in any set of digits that you choose.  But you might be able to disprove the fact that there's some particular image in there.  Actually, I don't think even that is disprovable.

Speaking of people who can't input Greek letters, http://dis.4chan.org/read/prog/1263084534/1-40.

OP here...  I just figured out that the digits (in binary) of sqrt(5) are exactly the same as the digits of phi, with the exception of the first two.  So, all I need now is a square root algorithm.

>>8
The only conclusion I see made in that thread is basically "to find a chosen string of digits "N" in the digits of pi, you will need to go to the Nth digit of pi, on average.  So to find your ten digit phone number in pi, you'd need to look at 10¹⁰ digits of pi, on average.  That's acceptable.

>>7
All possible images of finite size exist in there.
http://en.wikipedia.org/wiki/Borel%E2%80%93Cantelli_lemma

>>10
That requires the assumption that the digits of phi (or pi, etc) can be treated as a sequence of purely random events.

I predict that somewhere in ϕ is some representation of this image:
^{_{QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQWWWWWWWWm##BWW#8SvawQWWQQQQQQQQ
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQWZZ##ZZZZZXX22nnnnvvI?YdQQQQQQQQQ
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQWmm#ZXZXXXXSnnvvvvonvli|IWQQQQQQQQ
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQW##XSSSS2onnvvvvIvoovv|+++?HQWQQQQ
QQQQQQQQQQQQQQQQQQQQQQQQQQQQWWWmWWWWWWWWQQQQQQQQQQQQQQQQQQQQQQQQQWWX2oooo1llli|lillvvvvi|=:-:+{3WWQQ
QQQQQQQQQQQQQQQQQQQQQQQQQW#m####XX2X22oSX#WWWQQQQQQQQQQQQQQQQDX$W#nnn1vnli||+===-:=+i||l|=:.  =||VQW
QQQQQQQQQQQQQQQQQQQQQQQW###mZXXon1vvv2XZ#ZXZZ#mQQQQQQQQQQQQQAom#Xlliilvvlli==:. ...:==|||=:.   +v%3Q
QQQQQQQQQQQQQQQQQQQQQW#ZXSXSXYIllIvnoXXX#Z##mBWQQQQQQQWWWQQ#XW##e>+=|lvvli|+=:.. . ..;====;     -<l3
QQQQQQQQQQQQQQQQQQWWXX11no1Iilvlivvnoom#mWmmmQWQQQQQW##WWQEnW#B}--.;+iIvl|+=;.     . .;===;.     =|v
QQQQQQQQQQQQQQQQBXZn1lIvIiiii%||llvvmm#m#####WWQQQQW#Z#WWDvWXW}-. ..=|llii||=; .     :=+=||%v>.  -=I
QQQQQQQQQQQQQQW#1o1vlili|i||%=|i|ivXXX#U#ZZXmWQQQWm##X#mWoXX#Z>..  :aqgwo2lisi;.    .<vviilvY*i. .|>
QQQQQQQQQQQQQWGvvll||||=||||=+|=|ioSXZXXSSomQQQQWmm#XX#BGevv3Xz;=  vWWZYY}<vIns:  ..:i|++~-  ..  :|>
QQQQQQQQQQQQQZnli||=||=|+|===+==|vo#ZXS22S#WWQQWWW#XXXmWli<i3#hii. 3X(:/   -+l|..  :||: .        =|:
QQQQQQQQQQQQ#n}||+=;====;:::===|inZZXn2oXXXWBQWWWm#X2mWZii<i3Zmvn= -I:-     :iIsa>=vov:          |+.
QQQQQQQQQQQB2I||=:::=:::.:.:::=|i2XS1oXZXoX##Q#WWW#oX@1eii|IvX#ZXc  <i=,  . _vumQmqmmXa=___;.   .=|
QQQQQQQQQW#oi|||=:::::.:.:.:.:=|vno1vXZonvommWQWQWXoW|<1=i|iivXXXc. -+1XuwosumQQWQWWW#Xov|i=    :==
QQQQQQQQQWWhi|=:::=;:::=:::-:=|ilvnlnXnnwXZ#$WQQW#XXk>ic+i|i|lvXo1=   =vXmm##BBWWWWm#X2l|+|=   .;=`
WWWWWBWW##XS>=;;=;;====::;:;:+||lIlinnomWS1oQWQQW#XX2s%l|Illi||Ioov=. :{Xm##ZmmW#USX1o1vi|+=  .;== 
mmmZZ#####Xn>=;;;:=++=.::=:=+|||i|||nq##X1ld#WWQB#XnhoiiivliI|+=nXov;  =3##X##m#ol+|lvnvv|==  .=== 
XX#SXXXXZXqh>=;::==:::==:; :==||+||<dXZ21sdG#mQW#Xom#Silii><i||=v3mv|  .)XSX##ZXn|=:={2oivi=. .=== .
SX#X#ZXXX$mos==.==:::===: .:-=+==|=io*llvndnmWW##2XmZXXvIi=:|:=ii3mz+   +lvXX#21l=:::=+Ivvi>   =||..
1nClv211XX#Ssi;=|===|==;  .: :;=;==i||vXoSodZm#Z2d#X2XXes|==l:=vnmmX|   .<lvmZXc==:. .. -~<|:  -|=|.
1n2vvooooXZ2s=-=====|+=.:.:: ...:;=:in11nnXX#ZXoXZ21nnnzvivi|.<vXW#e=    =ldmmX}--:. .    :Ii.  ==:|
oXZXXXXX###mz====+.||+::=;:..   ::=<vlv1ndZm#2oXXXvInlvXsnvii=|I3WX1;    <vQWWQc  - .     :i|...;=;<
211vn1vnnoXmoi===+.=||:===..   ..:<><nvo#Z#m#oXSonvivvoXo2vvvvvnd#1v;    =vWWW#X;.        =i|=.:.:=<
ilivvlsvvXmmZs>=|===+|=:+;;.. .  .=ivnXSXXXmZnn2nnvInXZXenlvvInn3Sli;    -vWWWmXv;       .||ina...:<
iivvvlvIXZQW#1:+=-+=|+i;=;:.     :=<lnvXXnd#Xnn2o2nlnXolliiIliiil1||=     3#mW#X1=-..   .:||uQQ:::=<
liiivIvnqmW#Xl<%:.==|=|;.::... ...-|{Iv#XomUXodo22nin2ol>|+l||=++|++=;.    )UXXYl|==- -:,=iwQQW.%==|
l|lvvlvdUXSSeii> ==+>=+:=::.   .:.;=<|nXSo#Z2nXX22n|nnnI|==|=|====+=|=;.     ~^--     .<nnmWQQQ=S>|+
=iii|llvI{dSv=i` -.=`==+- .   .:.::=<lnSoZSe2nXXnXo|IloI=:;+==::::==+=:. .           :=il2XS$WW(nn||
|i|<%+<%v|vol==: ..:.=-`     ....;===|InnlIiooZ2vZXil|ni==:;=-.:.:+=+> .            .-:<nmXwuvIil1==
|=|%i+|=|<nl> .- .:..:    .. :..:=-.;=Iii++vnXXnvZ2Ii|v>=; :: .: ==|+;...            .:|nQmQWWmuuaii
==|i>={*}*I{> .  : :...: =: ..::: ..;<i+`:<vo2vInZnv|iv==.    . ..==== . ..          .:<dmQQWWmmmXXX
|||||=<>=iI%` .  : :..=;.= ..::.  . =+=:._vionvvX2ii=ii::.        ..-- . .         . .=idWQQWWWmm###
|++=+|=>:=v>:;     : :== : . +;.   --:.=|vIoonvo2ii>=||..         :: ._..           ..<n#QQQWWmBm##Z
<=|i%=i|iuci|:.     ..-. . . :i;.    .ivvivoonnnn=v=|==:..       .:. =..        .   .:vmmQQWWWWBm##X
|v1vavnI11*!*+=.  . ..      .:+==:.  :<vvonn1vlli=I+|-;.:        .- .=:.         ...:<X#WWQQQWmmm##Z
. -.::;===+++|+=     ....  .:==+|+=. :<vIlvviiiisi><| =..        . ..=:.    .  :..-::i<2X##WmWmm##ZZ
.......:::::=:;=:   .. .:::;::;:==vc -===|I>=ivil<:<|.::.   .     . ::. .  .  .  ..=v,="{vvYXX###XZX
   . .  .:...-.;+ .   ..=;:+===;;={p:.;;=%=.%Ill>===i::-. . ..   .  .:. - . . .:.:.:.""ns."+<I*1no2X
     . .. .. ..;=.    :::..- ..:-=3"`  ;|:=%lll>==>.|`: : :    . .   ::  .:.-..:::;     -?a,:^<i||{l
        - :.  -=;       :=. .-:.-.     ===Iii|++=+:==.     . ..;..    -  ::  ..;::.        "4a, -~|-
      .      .  .       .-:=          .+=|>|=|=;= =: .    .   .;..        .. .-::... .     .  "1a  
           .    -.          `        .=|+=|||===.=;:         .=;;.        . ..=:. .             -?s,}}

You will have to modify it yourself for it to work in positive integer bases greater than 10, but as long as you're willing to write the lookup, it's no problem.

#lang racket
(define stream-car car)
(define (stream-cdr str) (force (cdr str)))
(define-syntax stream-cons
  (syntax-rules ()
    ((_ a b) (cons a (delay b)))))

(define (make-consumer-emitter-base base a b c d cf)
  (define (consume)
    (let ((t (stream-car cf)))
      (let ((a (+ b (* a t)))
            (b a)
            (c (+ d (* c t)))
            (d c))
        (make-consumer-emitter-base base a b c d (stream-cdr cf)))))
  (define (emit?)
    (cond ((or (zero? c) (zero? d)) #f)
          ((= (quotient a c) (quotient b d)) #t)
          (else #f)))
  (define (emit-base)
    (if (not (emit?))
        (consume)
        (let ((t (quotient a c)))
          (let ((a (* base (- a (* t c))))
                (b (* base (- b (* t d)))))
            (stream-cons t (make-consumer-emitter-base base a b c d cf))))))
  (emit-base))

(define (endless n) (stream-cons n (endless n)))

(define (print-phi base terms)
  (let ((phi (make-consumer-emitter-base base 1 0 0 1 (endless 1))))
    (display (stream-car phi))
    (display ".")
    (let loop ((terms (- terms 1))
               (phi (stream-cdr phi)))
      (if (zero? terms)
          (newline)
          (begin
            (display (stream-car phi))
            (loop (- terms 1) (stream-cdr phi)))))))
Then we have
(print-phi 10 200)
1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374847540880753868917521266338622235369317931800607667263544333890865959395829056383226613199282902678
 (print-phi 2 200)
1.1001111000110111011110011011100101111111010010100111110000010101111100111001110011000000011000000101110011101101110010000011010000010000100000100010011101101011111100111010001001110010010100011111100
 (print-phi 7 200)
1.4216620364601603551416420422051024134413051314542065442606120223611643055123125052056034432031040006345162232600450412156045033022614052460642253200441343114512413224021032644530234441552062542113430

Enjoy.

>>13, please stop using odd streams, thank you

>>14
For a one-off problem, even streams are a fucking pain in the ass because now your lambdas have to be stream-lambdas and  etc. Kind of irritating. But otherwise I would.

>>13
Oh my.  Now, if I can just extract pseudocode from this... pseudo-code, I'll be off and running.

>>16
If you are hunkering down on phi specifically, many optimizations can be made. All that is important for your task is understanding the play between consume and emit. The rest of it is just implementation details.

I happened to spend my weekend working on a continued fraction calculator so this is very fresh in my mind, and I just recreated this in the same style. Therefore it is a bit too generalized for the particular problem in the OP, even though I did spend at least three seconds thinking about tightening it up for these requirements.

Phi is actually a very convenient number to work with, since its first term is 1, meaning you don't need any special work to print the first term. But I didn't feel like coming up with an arbitrary number->base-string function. That's all display crap, anyway... what you get out of consumer-emitter is just the number you need to display (after possibly the first term). For example, avoiding the display routine here's a base-16 expansion (imagine a decimal point after the first number):
'(1 9 14 3 7 7 9 11 9 7 15 4 10 7 12 1 5 15 3 9 12 12 0 6 0 5 12 14 13 12)

>>16
His code looks and runs fine, what is the problem?

>>12
It's 44x100 = 4400 characters.  It uses the following characters:
!"#$%()*+,-./12348:;<=>?@ABCDEGHIQSUVWXYZ^_`acdeghiklmnopqsuvwz{|}~
That's 68 characters.  So, you'd need to look at something on the order of 68⁴⁴⁰⁰ digits of phi to find your image.

>>19
Not implausible but the coefficients of the matrix grow faster than they shrink. Eventually you will run out of memory, or worse, if you're using fixed point integers, you'll overflow and produce erroneous results. For example, after printing (1 39 35 29 57 46 23 61 10 31 1 23 51 39 12 1 32 23 14) in base 64 one of the coefficients has exceeded 2^64. Overflow isn't a problem for Racket but of course there'd be issues with some naive implementations in C etc.

>>18
His code looks and runs fine, what is the problem?
>>1
ask that it be in C

>>19
>>20 here, obviously printing that many digits is a massive problem, I was more referring to printing in base 68.

>>21
With enough time on their hands I am sure a reasonable person could translate the core of this to C. If they cannot manage to do this and use gmp then there's no point. Just go to wolframalpha, as anything else is beyond them.

>>20
There's no algorithm for computing arbitrary digits of a square root that doesn't consume an unbounded amount of memory?

You don't need to keep the entire result in memory, if that helps.  If you're searching for a 32x32 image, for example, you only need to store 1024 bytes of the result at any given time.  So, you should be able to search forever unless the algorithm itself requires unbounded memory.

>>23
You'd have to dig up a spigot algorithm for roots. They exist, but in the thirty seconds I spent searching I couldn't find it freely available.

"Spigot algorithm," interesting.  There are plenty of these available for pi.  I guess it's dumb to do phi just because I have a personal preference, when pi is readily available.

>>25
Not necessarily dumb. If the means to work out pi are readily available, what fun is that?

>>25
The problem is spigot algorithms are tied to base representations. I haven't looked at them in a while, so I don't remember if there are constructions for arbitrary bases, but I doubt it. There is certainly a spigot algorithm for base 16 expansion of pi, which would automatically give you bases 2, 4, 8, 32, etc., but I don't remember if there are others.

I may have found it...
http://www.numberworld.org/programs/

>>1,28
Why can't you just write one yourself? It's elementary math.

>>29
see >>24

Dumps one million base-n digits to a file. Ran this last night to see how slow it is.

(dump-phi)
Base 2
cpu time: 711957 real time: 713313 gc time: 193103
Base 3
cpu time: 2399654 real time: 2402177 gc time: 876636
Base 4
cpu time: 3802150 real time: 3802648 gc time: 1372564
Base 5
cpu time: 5054604 real time: 5054148 gc time: 1831384
Base 6
cpu time: 6151884 real time: 6151631 gc time: 2207421
Base 7
cpu time: 7106438 real time: 7106013 gc time: 2513587
Base 8
cpu time: 8020698 real time: 8020364 gc time: 2848794
Base 9
cpu time: 10084232 real time: 10083881 gc time: 4354536
Base 10
cpu time: 10915873 real time: 10915227 gc time: 4690351
Done

35 Name: Anonymous 2010-12-22 13:53

36 Name: Anonymous 2010-12-25 14:00

37 Name: Anonymous 2011-02-03 2:35

Don't change these.

Name:		Email:
Entire Thread Thread List

All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -