newton functional

newton_functional.rb

require 'benchmark'
@mod_256 = [true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false]

def approx_root(len,divisor,n)
  return n if n < 100
  len <= 1 ? (return (n / divisor)) : approx_root(len-1,divisor*10,n)
end

def isqrt(guess,n)
  guess**2 - n  < 0.5 ? (return guess) : isqrt((guess+n/guess) / 2,n)
end

def perfect_square?(n)
  @mod_256[n%256] ? isqrt(approx_root((n.to_s.length - 3).abs / 2.0,10,n.to_i),n)**2 == n : (return false)
end

def is_fibonacci?(n)
  perfect_square?(5*n*n - 4) || perfect_square?(5*n*n + 4)
end


puts is_fibonacci?(100*60)
puts is_fibonacci?(3)
puts is_fibonacci?(28657)
puts is_fibonacci?(34)
puts is_fibonacci?(8670007398507948658051921)
puts is_fibonacci?(2**12345) 
puts is_fibonacci?(193512580117753337173264405486283449497476393398565859614123245899135148015930921275940266184649379538324496329922225713011127590681988097846969965015880966711479825338899008456977963462934877956409314933914995421930151202189026263783124370262815300222246626238881403039910418538340284864194944192887549331945656079110059730186900218744043704880477179552114283313254802257744015347379684516633567474079650607508044794590829175992677591620947479947563016300654766619006175887687575374152730555977535202607404181612536466665336419788131619507514736636771085154606300696479755652492224701660186510543173759382503561964167500299431680352738251645639322340076357544507538683978930112693369367144004798869888610415170896750097108400702836440442625436540322430660105790904382434951931916488060672156180652546845906652583746430708758842308542939952460579902953950172096457489147791120680668751196523048990162057947994380866964341983636470650641264666638278924124920715453744201859188338354753189671121860965300239927557177334062422816026824820033609567070020606735009024477982540094954036930222188763642708551014639985938671487165762104648623034659422125467624474646014854208844353716925237114952238095483909013522761998513382041467195544656163051153985354935768976625484007939097317655298150867488233457173502769456189663896871683847929518369567576696317848612479835758039669498985198147029629129225506600673802923369097588875443919550072706528239444608103569453981063788344444341729365553774350977878604393700992896444589468103821083240855241824934915979075118909871117605077299083389434154390193921269621348558680344283779192852576533502826476319586925781749159984860144149268199879780439978135152508927329339933995679947472010519395847217007623078487268603591497658353138175857487143080140103206998022614983445553926671907804004141851180595009460671424027236723809578752827126542328586798862384001356068828656938324046563615913677419713789769323546843000063275165598322695199786532779678209399961138733029712745980708099710103517917597255075872531180411913330481967354419399414361236746007947352611608725314740302326058264859142238041484778625147517395087737284402998957085524395982938221004463313275062210155824892461835518185519915317798875848999896228825387986442961785618186025273102622541053577419791216772932715033583221784653167059805439770810301212771703628657628848363852286434235643707563510554148747903948678818952440969637037124868594995491153253783617137559789800529571470935530937277319782939473817679295019503881819716223371260907919269897882937047660107553547321103411500274497967678850343721729689681902080622435551772580500923004556081674435695854105617996676198231712258305840846928271664607593547751002607330582188293518286859949965641229859717389328533639459434582120457028077404316105812444166839230369542058771360354655518502256867805960186736948761728259623724973749889134345242634186363190537962399782633497261164218399929857535517415793111818604017867105750182564732347886473772534884174445434001304168279532306614675109455318105840357168224068811425414027292489448112996813725519147586094200639395175364125487291468226511614682357188539635878581661412521727780099285332510788122225977068048785918985314671860025594306494610294096181232442321207099018468920160876366027692293837725742753622626036085607131716026384273092041792279934240149482015869838743846407135456522525257463114763811173762126771649874354027859021204314337285857470816866213146222448249992687723611292733536976837201554946000989392404014014538186892430453879561892840250988251184267296377425899051692358238338143274211985054910452315182176807468768102934500661229050241137437388645593952871302607569051536387788596713628419488)
puts is_fibonacci?(1589714236103231805807845743814491510543724551728352182180619573340909555187755725661038975685078205033274489440594239698496556688019174468805373160486798931679592801423359128214840033834124465952281515708797720482440146886172356743270623301621474009817203641084973875966149442907594479136773560361254035309911931155097839269910743030094126883225620828490006972780127821301937845863957744127938894659048549224731929249498943778859785586159498409041855551391612757676123419982543805965291689120254815036201417702125490869578270236120722297498178066187891743963336482927745821549245622757694266109048566242830974075366823274950370145124761574084786266590508614097025393313286551375059446293066805202110365000767320744515723814839190874082273755208612082957274061809351721011786034953916370603620099914175571494960553919231859061158655446067110259014679553305721309161281164540774210714728385409109094589033354395990180589838626738532455400035122162132534790748182233249260676401008954817263395765468207240616913425969608080798065159972797888273275023639105896283398101489112048498625143050584642657013247331392955707769630924893656853779438970169503934862671496830731033869511599782090812365640208222056285520090352243901137489254486160641430925574377801587307099400921112704057338809587728863182558402977325580583608977891795725094563062021525649884069074950937368304606759692688214064684972529759405921241367036677759517555399327440598371054464291834552964948878822961245659975779985502987145988499822007033586504631063754768844565494846394276240887793051620077948381281667588249178393094301974529489115516183908872391431230797)
puts is_fibonacci?(1589714236103231805807845743814491510543724551728352182180619573340909555187755725661038975685078205033274489440594239698496556688019174468805373160486798931679592801423359128214840033834124465952281515708797720482440146886172356743270623301621474009817203641084973875966149442907594479136773560361254035309911931155097839269910743030094126883225620828490006972780127821301937845863957744127938894659048549224731929249498943778859785586159498409041855551391612757676123419982543805965291689120254815036201417702125490869578270236120722297498178066187891743963336482927745821549245622757694266109048566242830974075366823274950370145124761574084786266590508614097025393313286551375059446293066805202110365000767320744515723814839190874082273755208612082957274061809351721011786034953916370603620099914175571494960553919231859061158655446067110259014679553305721309161281164540774210714728385409109094589033354395990180589838626738532455400035122162132534790748182233249260676401008954817263395765468207240616913425969608080798065159972797888273275023639105896283398101489112048498625143050584642657013247331392955707769630924893656853779438970169503934862671496830731033869511599782090812365640208222056285520090352243901137489254486160641430925574377801587307099400921112704057338809587728863182558402977325580583608977891795725094563062021525649884069074950937368304606759692688214064684972529759405921241367036677759517555399327440598371054464291834552964948878822961245659975779985502987145988499822007033586504631063754768844565494846394276240887793051620077948381281667588249178393094301974529489115516183908872391431230795)
puts is_fibonacci?(982497430311372448403168197173885335038992010285198549098750136561357444286160025235744365503973238613646420450040419586314714059693530326202567685324476279107158103631457018017630431281225889632645622987648706013568805573187411036537444721418212014713812155742696750860184763804035810917010330656852080201474593334686005803259843247980484161614204805465170648752468908458819089214620908925300129896913837326636377747066528877400769396794411292904340982216386516969338704758133121431987437242144202721347264723060253974519469013676891650198421809067399495877290307005922441132437440464185049208156451253079636768764020303289953156594603180424462180288366805576222713696953494347438393940510176133469107637522892895683050277761611971575287356702497900002769211655225452328134139525038967353601875104279733303752941491324365564946757034711918239364052813827012530177196272786311742615177602251819534205728964879212981356290150886737618391938312571468644049318879917453630376042905669192385801582453019170202586475631743870295550828431737716717943763552661905895568833942389807169674350931959422471045654424965552862801069471099037201615938201647101546710239719467862671406555004498140996108591312494731447370865319505787609258409091524727384233149928860378756825147509494368593973364819300835470824195114800955957724713625259041407782654096501167914767318209600791997011602297739138257766828319028304990037578282701205687223775211437556700370081675877271660391196607240233996638623842285051899734625936998742683207830883191090213713043541921110886303120041968514434413076713458682974567896573145511229176877264035332259923271816)


puts Benchmark.measure {is_fibonacci?(100**20)}
puts Benchmark.measure {is_fibonacci?(3)}
puts Benchmark.measure {is_fibonacci?(28657)}
puts Benchmark.measure {is_fibonacci?(34)}
puts Benchmark.measure {is_fibonacci?(8670007398507948658051921)}
puts Benchmark.measure {is_fibonacci?(2**12345)} 
puts Benchmark.measure {is_fibonacci?(193512580117753337173264405486283449497476393398565859614123245899135148015930921275940266184649379538324496329922225713011127590681988097846969965015880966711479825338899008456977963462934877956409314933914995421930151202189026263783124370262815300222246626238881403039910418538340284864194944192887549331945656079110059730186900218744043704880477179552114283313254802257744015347379684516633567474079650607508044794590829175992677591620947479947563016300654766619006175887687575374152730555977535202607404181612536466665336419788131619507514736636771085154606300696479755652492224701660186510543173759382503561964167500299431680352738251645639322340076357544507538683978930112693369367144004798869888610415170896750097108400702836440442625436540322430660105790904382434951931916488060672156180652546845906652583746430708758842308542939952460579902953950172096457489147791120680668751196523048990162057947994380866964341983636470650641264666638278924124920715453744201859188338354753189671121860965300239927557177334062422816026824820033609567070020606735009024477982540094954036930222188763642708551014639985938671487165762104648623034659422125467624474646014854208844353716925237114952238095483909013522761998513382041467195544656163051153985354935768976625484007939097317655298150867488233457173502769456189663896871683847929518369567576696317848612479835758039669498985198147029629129225506600673802923369097588875443919550072706528239444608103569453981063788344444341729365553774350977878604393700992896444589468103821083240855241824934915979075118909871117605077299083389434154390193921269621348558680344283779192852576533502826476319586925781749159984860144149268199879780439978135152508927329339933995679947472010519395847217007623078487268603591497658353138175857487143080140103206998022614983445553926671907804004141851180595009460671424027236723809578752827126542328586798862384001356068828656938324046563615913677419713789769323546843000063275165598322695199786532779678209399961138733029712745980708099710103517917597255075872531180411913330481967354419399414361236746007947352611608725314740302326058264859142238041484778625147517395087737284402998957085524395982938221004463313275062210155824892461835518185519915317798875848999896228825387986442961785618186025273102622541053577419791216772932715033583221784653167059805439770810301212771703628657628848363852286434235643707563510554148747903948678818952440969637037124868594995491153253783617137559789800529571470935530937277319782939473817679295019503881819716223371260907919269897882937047660107553547321103411500274497967678850343721729689681902080622435551772580500923004556081674435695854105617996676198231712258305840846928271664607593547751002607330582188293518286859949965641229859717389328533639459434582120457028077404316105812444166839230369542058771360354655518502256867805960186736948761728259623724973749889134345242634186363190537962399782633497261164218399929857535517415793111818604017867105750182564732347886473772534884174445434001304168279532306614675109455318105840357168224068811425414027292489448112996813725519147586094200639395175364125487291468226511614682357188539635878581661412521727780099285332510788122225977068048785918985314671860025594306494610294096181232442321207099018468920160876366027692293837725742753622626036085607131716026384273092041792279934240149482015869838743846407135456522525257463114763811173762126771649874354027859021204314337285857470816866213146222448249992687723611292733536976837201554946000989392404014014538186892430453879561892840250988251184267296377425899051692358238338143274211985054910452315182176807468768102934500661229050241137437388645593952871302607569051536387788596713628419488)}
puts Benchmark.measure {is_fibonacci?(1589714236103231805807845743814491510543724551728352182180619573340909555187755725661038975685078205033274489440594239698496556688019174468805373160486798931679592801423359128214840033834124465952281515708797720482440146886172356743270623301621474009817203641084973875966149442907594479136773560361254035309911931155097839269910743030094126883225620828490006972780127821301937845863957744127938894659048549224731929249498943778859785586159498409041855551391612757676123419982543805965291689120254815036201417702125490869578270236120722297498178066187891743963336482927745821549245622757694266109048566242830974075366823274950370145124761574084786266590508614097025393313286551375059446293066805202110365000767320744515723814839190874082273755208612082957274061809351721011786034953916370603620099914175571494960553919231859061158655446067110259014679553305721309161281164540774210714728385409109094589033354395990180589838626738532455400035122162132534790748182233249260676401008954817263395765468207240616913425969608080798065159972797888273275023639105896283398101489112048498625143050584642657013247331392955707769630924893656853779438970169503934862671496830731033869511599782090812365640208222056285520090352243901137489254486160641430925574377801587307099400921112704057338809587728863182558402977325580583608977891795725094563062021525649884069074950937368304606759692688214064684972529759405921241367036677759517555399327440598371054464291834552964948878822961245659975779985502987145988499822007033586504631063754768844565494846394276240887793051620077948381281667588249178393094301974529489115516183908872391431230797)}
puts Benchmark.measure {is_fibonacci?(1589714236103231805807845743814491510543724551728352182180619573340909555187755725661038975685078205033274489440594239698496556688019174468805373160486798931679592801423359128214840033834124465952281515708797720482440146886172356743270623301621474009817203641084973875966149442907594479136773560361254035309911931155097839269910743030094126883225620828490006972780127821301937845863957744127938894659048549224731929249498943778859785586159498409041855551391612757676123419982543805965291689120254815036201417702125490869578270236120722297498178066187891743963336482927745821549245622757694266109048566242830974075366823274950370145124761574084786266590508614097025393313286551375059446293066805202110365000767320744515723814839190874082273755208612082957274061809351721011786034953916370603620099914175571494960553919231859061158655446067110259014679553305721309161281164540774210714728385409109094589033354395990180589838626738532455400035122162132534790748182233249260676401008954817263395765468207240616913425969608080798065159972797888273275023639105896283398101489112048498625143050584642657013247331392955707769630924893656853779438970169503934862671496830731033869511599782090812365640208222056285520090352243901137489254486160641430925574377801587307099400921112704057338809587728863182558402977325580583608977891795725094563062021525649884069074950937368304606759692688214064684972529759405921241367036677759517555399327440598371054464291834552964948878822961245659975779985502987145988499822007033586504631063754768844565494846394276240887793051620077948381281667588249178393094301974529489115516183908872391431230795)}
puts Benchmark.measure {is_fibonacci?(982497430311372448403168197173885335038992010285198549098750136561357444286160025235744365503973238613646420450040419586314714059693530326202567685324476279107158103631457018017630431281225889632645622987648706013568805573187411036537444721418212014713812155742696750860184763804035810917010330656852080201474593334686005803259843247980484161614204805465170648752468908458819089214620908925300129896913837326636377747066528877400769396794411292904340982216386516969338704758133121431987437242144202721347264723060253974519469013676891650198421809067399495877290307005922441132437440464185049208156451253079636768764020303289953156594603180424462180288366805576222713696953494347438393940510176133469107637522892895683050277761611971575287356702497900002769211655225452328134139525038967353601875104279733303752941491324365564946757034711918239364052813827012530177196272786311742615177602251819534205728964879212981356290150886737618391938312571468644049318879917453630376042905669192385801582453019170202586475631743870295550828431737716717943763552661905895568833942389807169674350931959422471045654424965552862801069471099037201615938201647101546710239719467862671406555004498140996108591312494731447370865319505787609258409091524727384233149928860378756825147509494368593973364819300835470824195114800955957724713625259041407782654096501167914767318209600791997011602297739138257766828319028304990037578282701205687223775211437556700370081675877271660391196607240233996638623842285051899734625936998742683207830883191090213713043541921110886303120041968514434413076713458682974567896573145511229176877264035332259923271816)}

# Results :
# 0.000000   0.000000   0.000000 (  0.000116)
# 0.000000   0.000000   0.000000 (  0.000016)
# 0.000000   0.000000   0.000000 (  0.000010)
# 0.000000   0.000000   0.000000 (  0.000007)
# 0.000000   0.000000   0.000000 (  0.000029)
# 0.020000   0.000000   0.020000 (  0.017454)
# 0.010000   0.000000   0.010000 (  0.017371)
# 0.010000   0.000000   0.010000 (  0.002959)
# 0.000000   0.000000   0.000000 (  0.006442)
# 0.010000   0.010000   0.020000 (  0.004120)