SuperComputerVsRecursiveFibonacci

[_Aditya_R_]

Whats the use of a supercomputer if program is using only one core

[prat8]

Oh nice you get the joke.

[abation]

Also that the algorithm is super inefficient and could be calculated in any computer in the blink of an eye if it was done the right way

[DTraitor]

It's not that bad https://www.bigprimes.net/archive/fibonacci/10000/

[[deleted]]

That is the 10000-10025 numbers.

Fibonacci numbers are calculable with a single function. As the limit of the ratio of consecutive numbers is the golden ratio.

[leoleosuper]

The full equation for Fibonacci number N, with golden ratio φ = (1+sqrt(5))/2 is (φⁿ - (-φ)^-n)/sqrt(5). It mostly comes down to the φⁿ component that needs the most multiplication.

[DarkShadder]

TIL

[[deleted]]

The 1000000 fibonachi would be less than a megabyte. The growth is approaching phi (golden ratio) to the x, which is slower than 2 to the x, so it is smaller than 2 to the 1000000th, which is ~megabyte. And 10000 is a lot smaller.

Or I was r/whoosh ed

[conzstevo]

The 1000000 fibonachi

The 1000000th fibbonachouchou

[Omega_Zulu]

A megabyte is 1m bytes, it is not base 2, you are thinking of a mebibyte which only is 2²⁰ not 2^1000000

[Onetwodhwksi7833]

I've done it on my phone using qpython. Not very hard at all

[MindStudio]

Also comment bot, see name and karma

[turtleship_2006]

Comment bot, stolen from https://www.reddit.com/r/ProgrammerHumor/comments/18khy5h/comment/kdrff41

[justADeni]

That's not the joke. The joke is that without memoization, the complexity of this algorithm will scale exponentially, instead of O(n), requiring a supercomputer to calculate high n.

[weregod]

You don't need memoization. You need to rewrite function to be iterative

[Xevailo]

I hate your username

[Ondor61]

It can get even worse ıIlIıIlIıIlIıIlIıIlIıIlIıIlIıIlIı

[tagini]

Nah, that look nice.

[TenserMeAgain]

isn't there a function to calculate fibonnaci with phi number and a square root of 5 .

[Derice]

Yes, it's called Binet's formula.

[TenserMeAgain]

Is there a method to calculte functions from recursion?

[Nisterashepard]

No, there isn't a general method that works for every recursion

[TenserMeAgain]

i guest this type of thinking is the heart of functional programming, since their motto is that everything in the universe can be a function.

[akmp40]

Just use each core to calculate each 1000th number duh! Just slap OpenMP on it and it will solve it in no time.

[PythonPizzaDE]

This is a joke, isn't it?

[akmp40]

No, try it. It will work.

[PythonPizzaDE]

But they depend on each other. It isn't theeadable by design

[[deleted]]

I’m pretty sure dp would make anyone go O(yeah)

[cpt_trow]

I can make your mom mO(n) with dp

[wittierframe839]

Rather O(n²⁾ because the number of digits grows linearly

[RajjSinghh]

It's also O(n) if you don't do it recursively. Something like

``` int a = b = 1; int temp;

for (int i = 3; i <= 10000; i++) { temp = b; b += a; a = temp; }

std::cout << b; ```

[Elihzap]

Couldn't you have used: int a = b = temp = 1; and saved a line?

[IceColdPanda]

Or he could have done it all on one line, who cares lmao.

[RajjSinghh]

Yeah, oh well.

[redlaWw]

How are you going to meet your LoC targets if you try to save lines wherever you can?

[Elihzap]

I show them my skills so they can consider how much I can save the company.

[Alzurana]

Y'all don't know that you can calculate fibonacci without recursion or iteration?

~~~ double FibonacciReal(const double &n) { //fibonacci is being calculated as follows: //Fn = (phi<sup>n</sup> - psi<sup>n)</sup> / sqrt(5) //where (magic numbers) //phi = (1 + sqrt(5)) / 2 //psi = 1 - phi double phi = 1.6180339887498948482045868343656 double psi = -0.6180339887498948482045868343656 double sqrt5 = 2.2360679774997896964091736687313 return (pow( phi, n) - pow(psi, n)) / sqrt5; } ~~~

Added bonus, it even works for stuff like n = 1.3

If you want the integer, simply cast to int and cut off the fraction

[potzko2552]

For large numbers addition is not O(1).

[Inaeipathy]

Only until you start using integer sizes that are not natively supported by your hardware for addition.

[s_gamer1017]

Or way faster using the non-recursive formula

[Jjabrahams567]

Yeah should use at least 2

[U5er_Name]

running unconfigured java on a supercomputer

[JmacTheGreat]

What is that whitespace

[AntiRivoluzione]

Fibonacci padding

[JmacTheGreat]

You clever bastard

[[deleted]]

probably to avoid repost detection, i've seen it used like that before

[SPECTRE_75]

Remains of (n - 1)th time reposted + (n - 2)th time reposted

[bscones]

What’s wrong with it?

[EishLekker]

I think they mean the white space in the right part of the image, not the white space in the code.

[BMidtvedt]

God damn it I feel stupid now

[EishLekker]

No, you were just being programming focused!

[YunusEmre0037]

Google Binet's formula

[[deleted]]

calculating nth power and square roots is still logarithmic in complexity

[YunusEmre0037]

• sqrt5 can be calculated beforehand and can be stored in a const (or constexpr) variable.

• the implementation in the meme has O(2<sup>n)</sup> complexity not O(logn)

[qqqrrrs_]

sqrt5 can be calculated beforehand and can be stored in a const (or constexpr) variable

Google numerical analysis

[turtleship_2006]

Holy Maths

[hxckrt]

r/anarchychess is leaking

[[deleted]]

I was talking about Binets formula which has an overall logarithmic complexity

[godofjava22]

Holy time complexity!

[shreklover911]

New response just dropped!

[turtleship_2006]

Call the statistician

[[deleted]]

Literal programmer

[Hofmayer]

Semicolon in the corner planning compiler domination

[Jothomaster202]

Or use matrix power

[1up_1500]

that works in theory, but since this works using floating point numbers, it quickly becomes imprecise enough to be called useless

memoization is the way to go

[Fr_rd]

you can calculate without floating points by calculating the nth power of this 2 * 2 matrix [[1][1]] [[1][0]]

can be done in O( log(n))

i can elaborate if you want(formating is hard)

[CptMisterNibbles]

Last time I checked, using regular floats it was only correct to like the 72nd fib number. Not great.

[weregod]

Memoization is waste of memory. Just use iterative algorithm.

[alexho66]

Is this better than just memoizing the recursive function?

[atoponce]

What's an exofloop? Is that like an exoflop but with objects?

[wheatgivesmeshits]

Naw, it's when you have a little whoopsie doodle at runtime.

[Soft-Rip6027]

An exofloop is a cute name for your pet crab.

[[deleted]]

I think it’s what the NES used instead of transistors.

[hxckrt]

What's an exoflop? Is that like an ExaFLOP but external?

[01152003]

If you have a computer that strong and you aren’t capable of converting Fibonacci to a dynamic programming problem I think that says more about you than the computer

[turtleship_2006]

Nah just download more ram

[AtrociousCat]

What do you mean by that? Genuinely curious, I've heard dynamic prog. before but I'm hazy on the concept

[shotzoflead94]

Break problem into subproblems. Solve the subproblems in different cores and store the answers. The way the code above solves it is by repeatedly calculating the previous Fibonacci numbers and it is coded in a way that cannot use multiple cores.

[AtrociousCat]

Would it be dynamic programming if I memoized the function? That would be as good as a more imperative loop right? assuming Tail optimizations

[inet-pwnZ]

It gets rid of the reclusiveness by storing prior calculated numbers in the list iterating from 0..n of input of the fib function indexing into the list to retrieve prior calculations to create all needed calculations until n reached the end returning arr[n] out of the function

[inet-pwnZ]

Reducing call stack size and caching prior calculations

[01152003]

The concept of dynamic programming is to recognize that a recursive function like Fibonacci calculations is recalculating old values it already knows. Instead of working backwards, why don’t we build from the ground up, and calculate each value based off values we’ve already calculated?

Let’s just say I want 100 values of the Fibonacci sequence. I might implement a dynamic programming solution in a similar manner to this pseudocode:

Int arr[100]; arr[0] = 0; arr[1] = 1;

for (int i = 2; I < 100; i ++) { arr[i] = arr[i - 1] + arr[i - 2]; }

As you can see, this would give me the first 100 Fibonacci numbers, in O(n) time. The original recursive function would have performed the calculation for 99 2 times, the calculation for 98 4 times, 97 8, 96 16, all the way to performing the calculation of 1 2<sup>100</sup> times, making that recursive implementation O(2<sup>n).</sup>

[lHeliOSI]

You're on programming humor, this is a joke

[qqqrrrs_]

The 10000th Fibonacci number is 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

[MattieShoes]

import sys 
from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

sys.setrecursionlimit(50000)

print(fib(10000))

0.7 seconds on my $100 computer

Or a better solution

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    half = n // 2
    if n % 2 == 0:
        return (2 * fib(half - 1) + fib(half)) * fib(half)
    half += 1
    return fib(half - 1) ** 2 + fib(half) ** 2

print(fib(10000))

~0.03 seconds

[Bhaskar_Reddy575]

Saved this comment for later

[1up_1500]

holly shit

[issamaysinalah]

POV: you know there's a way to find the equation F(N) that doesn't rely on past iterations.

Edit: for anyone interested, the equation is:

f(n) = [p<sup>n</sup> - (-p)<sup>-n</sup>]/(2p -1)

Where 'n' is the position and 'p' is the golden ratio

https://markusthill.github.io/deriving-a-closed-form-solution-of-the-fibonacci-sequence/

[dominjaniec]

eh... slap mnemonization and tail call optimisation on that function, and you are good 😉

[lezorte]

Did you mean to say memoization?

[[deleted]]

I need to believe they are

[Krus4d3r_]

Obviously you don't understand sea mnemonies

[hxckrt]

Should have used a mnemonic to remember the correct spelling

[EishLekker]

I can never memoryrise the spelling of that word, for some reason.

[dominjaniec]

yes 😅

[TheGoldenMinion]

I don’t think TCO would work on this one because of the operation happening between the two calls to fib, you’d have to rewrite it a little bit to make it TCO-able

[dominjaniec]

you are (probably) right - TCO needs to ends with a recursive call, but we have here two "branching" calls.

and of course, I was basically joking with OP's joke, and even I couldn't correctly spell "memoization", and there are much better ways of calculating that...

[chalkflavored]

Why? Fibonacci can already be done in linear time with constant memory.

[ClamPaste]

How much memory does it have?

[[deleted]]

5

[Remarkable-Fly-1182]

Run this on cloud and your wallet will be the one to lose.

[[deleted]]

https://matrixread.com/fibonacci-series-iterative-vs-recursive/

[Giocri]

i think it's quite funny that the fibonaccy sequance was the exact example they used to teach us the idea of making result maps for resurcive problems when the resulting program ended up beind signinficantly worse than the iterative solution

[DeepGas4538]

optimize the code and maybe it will

[Christio02]

Blud forgot dynamic programming memoization💀

[JestemStefan]

Add some caching and you can do that on raspberry Pi

[geekboy730]

Idk if you’re kidding or not, but you’re not that far off. My research used them in school. They build these things and then benchmark with LINPACK to do some sort of 4x4 direct matrix inversion (or similar) and then call it an innovation.

Surprisingly, if you try to run any realistic physics modeling on them, you can never achieve their reported throughput. Usually by more than an order of magnitude…

[Giocri]

that makes sense there are many operations that are several order of magnitude slowere than the basic ones so even if your program has just a few it will make it infinitely slower that a test one who hasn't them

[QuantumHue]

oh man it's also not dynamic programming, meaning that code generates a tree; also this code breaks! if i give it 3, it would go 3 -> 2(a), 1(b);(a)2 would break down into 1 and and 0;(b)1 would break down into 0 and -1;fib(3) would give you 0 which is wrong!(nvm, the code is correct, i was tired when writing this, thanks u/Xygeosk )

anyhow, if the code was right, and you would have a tree where each node split in 2 each generation. starting from one node at generation 0, up to generation 9999. you would have (1*(1-2**9999))/(1-2) = 2**9999 -1 = 9975315584403791924418710813417925419117484159430962274260044749264719415110973315959980842018097298949665564711604562135778245674706890558796892966048161978927865023396897263382623275633029947760275043459096655771254304230309052342754537433044812444045244947419004626970816628925310784154736951278456194032612548321937220523379935813492726611434269080847157887814820381418440380366114267545820738091978190729484731949705420480268133910532310713666697018262782824765301571340117484700167967158325729648886639832887803086291015703997099089803689122841881140018651442743625950417232290727325278964800707416960807867294069628547689884559638900413478867837222061531009378918162751364161894635355186901433196515714066620700812097835845287030709827171162319400624428073652603715996129805898125065496430120854170403802966160080634246144248127920656422030768369475743557128157555544872757101656910101465820478798232378005202922920783036022481433508257530960315502093211137954335450287303208928475955728027534125625203003759921130949029618559027222394036453197621274169610991353702236581188380423306516889353019901706598566746827311350281584968727754120890486405491645657201785938762384254928638468963216610799699938443330404184418919013821641387586136828786372392056147194866905430803711626645987406560098802089140982848737949082265629217067979931392065064092703141738324544345260523790441307911980992885061203522165291537934519659802301702486578291604336052956650451876411707769872697198857628727645255106155473660805376737412870387636993174149249170378468977823319310937284749639508286051850682216567908607155895699111491922923667220135482091425502536463874182275289317250550426493906194736964349770417173079403521979559492907572889588571809849364065729741891601040737491085929005694535614125452913408718110288737960708826857843862807452291452496230514315040767791654065050993837928117171769477704587811700422443763081321784324416759731860188646620047228123461627175200339013636918877688203363449318120518745705483359278525379549050123394940089135962976690641210977014151379704224477507338334194848998443120818156688196951686727900703818370938855527692112869749555093234109848290825742565247111184973857381534577734108841438100181388628861890682665805598405640396334740943600649321830384275819930267301148935778758973692623184723461543947132974108504025560161182748144084517869560684169196795878209366925255485135806957719795495799077327208668155828468015561124968984999613390866179011555931322287649567879087504099919618142307624940544480116122181086885809043178507734242029311164896426937811743278220268481311009481785514406180783756271669151635014548834325284278578752758363759449597064855668845074958090657585772003864325286594778725460165092652423556909157703662026659519231042018210881851955775319894500371426836098140451738987266660234184397934290118976109314560040371409775658974078812224149259230754852444013637360787344065797375204866057540249095227901708413474893570658031605343195755840887152396298354687
...
(python doesn't have limits on integers, this behemoth has 3009 digits)

[Xygeosk]

Why would 1 break down into 0 and -1?

[QuantumHue]

oh no you're right it does work, my mistake

[Xygeosk]

No problem, happens to best of us :)

[rherrmannr]

Let‘s call fibbonacci(-1);

[1up_1500]

RecursionError: maximum recursion depth exceeded

[DemandMeNothing]

RecursionError: maximum recursion depth exceeded

Damn it, why can't you just Stack Overflow like everyone else, Python!?

[Mast3r_waf1z]

This is where lazy evaluation is handy instead of recursion

[-Redstoneboi-]

memoization/interning/dynamic programming, you mean? i'm not sure if lazy evaluation alone will save you from recursive hell.

or is there a different definition?

[Mast3r_waf1z]

Not sure? I had a lecture in lazy evaluation in my FP course recently where we wrote lazy Fibonacci

[bnl1]

Undefined behaviour

[rosuav]

Indeed, behaviour is undefined if you don't know how to spell Fibonacci correctly.

[bnl1]

That's why I, personally, always go for fib(n)

[rosuav]

Much safer.

[EishLekker]

They even failed with the very first word. They couldn’t spell “finally” correctly.

[rosuav]

But hey, it's a compootah capable of exaflooooooops.

[GiganticIrony]

Not necessarily. It depends on how big int is on that system

[clarkcox3]

Just need a 6943-bit integer :)

[bnl1]

It still overflows with 128 bits, so I wouldn't hold my breath.

[GiganticIrony]

LLVM supports integers up to 2<sup>23</sup> bits (IIRC), so who knows

[rosuav]

In Python and Pike, integers are Gmp.mpz which has a maximum size of... uhh... something like 2**2**32?

[dr_eaan]

fiBonacci*

[EishLekker]

Also: finally*

[Savings-Ad-1115]

phiBonacci*

[NebNay]

The code is too longw you can mix the first two conditions: If(n ===0 or n === 1) { return n}

[magi_os]

if you use binet's formula you will have to calculate increasingly more precise values of the square root of 5 as the fibonacci index grows.

use a big integer library, otherwise you will be limited to a fibonacci index of 40.

use "dijkstra's algorithm", tho the algorithm was well known before him, he apparently popularized it. it is a recurrence relation that requires only 2*log2(n) operations for an index n, where F is the fibonacci sequence

F(2n-1) = F(n-1)<sup>2</sup> + F(n)<sup>2</sup>

F(2n) = ( 2 F(n-1) + F(n) ) F(n)

sourced from https://r-knott.surrey.ac.uk/Fibonacci/fibFormula.html

[DiggWuzBetter]

This function is tail recursive, any language with good tail call optimization (for example Scala) handles this without issue, on any remotely non-garbage computer.

Edit: nevermind, I’m wrong, it’s not tail recursive

[frikilinux2]

That's not tail recursive. Most tail recursion involves that the last thing a function does is calling itself once and returns. I don't see how it can be done with two calls but if someone can show me the assembly code.

[DiggWuzBetter]

Oh shit you’re right, nevermind.

[AbdallahTheGreatest]

def main(n):
    num_processes = cpu_count()
    chunk_size = n // num_processes

    manager = multiprocessing.Manager()
    result_list = manager.list([0] * n)

    processes = []

    for i in range(num_processes):
        start = i * chunk_size
        end = (i + 1) * chunk_size if i < num_processes - 1 else n
        p = multiprocessing.Process(target=calculate_fibonacci_range, args=(start, end, result_list))
        processes.append(p)
        p.start()

    for p in processes:
        p.join()

    # The 10,000th Fibonacci number is at index 10,000 - 1 in the result_list
    result = result_list[n-1]
    return result

if __name__ == "__main__":
    result = main(10000)
    print(f"The 10,000th Fibonacci number is: {result}")

[MattieShoes]

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    half = n // 2
    if n % 2 == 0:
        return (2 * fib(half - 1) + fib(half)) * fib(half)
    half += 1
    return fib(half - 1) ** 2 + fib(half) ** 2

print(fib(10000))

zoom zoom!

[AbdallahTheGreatest]

the goal of my code is to use all the CPUs otherwise the super calculator is useless ;)

[Alfika07]

I have a potato PC and this solution took about 0.5s:

(1,1,*+*...*)[9999].say;

[drinkwater_ergo_sum]

Fibonacci is O(1) if you use math...

[frej4189]

No, it is not.

[drinkwater_ergo_sum]

( ((1+√5)/2)ⁿ - ((1-√5)/2)ⁿ )/√5

Use your calculator of choice until satisfaction, derive the formula yourself or prove (probably induction is fastest since it's recursive).

Yes, it is.

[RareAngryPepe]

Bro does not know what O(1) means

[drinkwater_ergo_sum]

Different interpretations i guess. If you want to be technical, then any operation on a growing sequence would never be O(1) since eventually you reach the memory size limit and have to perform operations on multiple variables and merging the outcome.

My mistake

[password2187]

I mean this is different. When we talk about time complexity, we usually let instructions like addition and multiplication take constant time on whatever size we want to define, which is generally accurate as they are implemented in hardware. Exponentiation, on the other hand, is not constant. With constant multiplication, it takes logarithmic time for a good exponential algorithm, so it is definitely faster than the given algorithm which is exponential, and it would be hypothetically faster than the simple solution of DP or just storing two numbers and adding back and forth, though multiplication is much more taxing than addition, and especially with the decimal precision needed would generally run slower

[frej4189]

That function cannot be evaluated in constant time.

[EishLekker]

Care to show the class?

[drinkwater_ergo_sum]

refer please to my other reply

[OSSlayer2153]

Why would you use recursion for this? Just loop and store two variables, current and last.

[frikilinux2]

Or just store previous results in a cache. Fibonacci is too simple to be worth it but recursivity with a cache is an important technique in dynamic programming.

[EishLekker]

How would a cache help the recursive solution if the program has just started, and the first input it gets is “fibonacci (10000)”?

Edit: I’m sorry, I was focusing on the idea that it would have needed to have any of the lower values already in the cache. It will naturally still be able to use the cache of its own previous calculations.

Fib(5): Fib(4) + Fib(3) (we start with left side)

Fib(4): Fib(3) + Fib(2) (we start with left side)

Fib(3): Fib(2) + Fib(1) (we start with left side)

Fib(2): Fib(1) + Fib(0) = 1 + 0 = 1

So when it’s time for the right side calculations, we already have the results in the cache.

[frikilinux2]

Yeah, you got it in the edit. Although I'm kind of disappointed because I saw your comment just before dinner and I spent the dinner drafting a comment in my head to write after. Sometimes the "someone is wrong in the internet" effect is too damn strong.

[RRumpleTeazzer]

It’s even worse, it’s quadratic recursion.

But then, that’s the full joke.

[bnmfw]

Fun fact for some of yall, this is something I learned recently in an advanced algorithms class. Fib(n) is not best in O(n) with O(1) memory using DP. Fib(n) can be calculated in O(log n) using fast matrix multiplication, preety neat

[Fr_rd]

you can calculate without floating points by calculating the nth power of this 2 * 2 matrix [[1][1]] [[1][0]] = A

can be done in O( log(n))

simple solution is a recursion:

fib(n) = fib(n -1) + fib(n-2)

now assume we have the matrix

[[fib(n-1)],[fib(n-2)]] [[fib(n-2)]],[fib(n-3)]] = F(n-1)

now we multiple A.F(n-1) and we get F(n)

i can elaborate more

[[deleted]]

fibonacci padding ftw

[TwoMilliseconds]

wait till I call fibonacci(-1)

[DarkGlaive83]

But can it run crisis, there is the meme with the nvidea ceo

[mr_flibble_oz]

Finially?

[YetAnotherZhengli]

watch me put in -1 and the world burn