Heater wrote: ↑
Mon Jun 10, 2019 9:47 pm
All challenges have rules. There is no challenge without rules.
One of the liberating aspects of personal computing is that the rules are decided individually between each person and their computer. Anything else would violate the principle of subsidiarity. One of the signs of the digital apocalypse is when all the rules are decided by a single emotional but powerful deep-learning neural network.
The fourth Fibonacci roundup compares three codes based on taking powers of the golden ratio for the purpose of laughing out loud to the simplest algorithm possible. Since no new PL/I or C codes were available, Python did a double shift: first as Python 2 labeled fibo_phi2 and then as Python 3 labeled fibo_phi3.
All timings were performed using the Raspberry Pi zero.
The Python code, though based on the fibo_phi.py code in the GitHub repository, was heavily modified as
Code: Select all
from decimal import *
n = int(input('? '))
if n == 0:
The exact same code was used for fibo_phi2 and fibo_phi3. Under Python 2 the asymptotic time complexity appears to be O(n^2.8) which is astounding. It is differently surprising that the Python 3 code behaves as O(n^2) for intermediate values of n. This may indicate that the crossover point between schoolbook multiplication and fast multiplication was chosen suboptimally. Alternatively, the strange shapes of the Python curves could reflect the computational time used in computing the high-precision floating-point approximations for sqrt(5) and its reciprocal that are needed for the numerical approach when using the golden ratio.
Only the main routine of the Pascal code golden.pas required changes to be compatible with fibench. The main routine was changed as follows:
Code: Select all
while true do begin
if n=0 then halt(0);
The LOLCODE haifibo.lol is not based on the golden ratio. Neither did it employ the doubling formulas, Karatsuba multiplication nor any other fast algorithm. The code posted here
was used unmodified. Although haifibo is the slowest code of the roundup for the values of n and Tn which appear on the graph, it would likely win over fibo_phi2 for larger values of n.