FIOC is SAF (Slow as Fuck)

While reading my SICP, I found a neat fibonacci function that has log n operations. I looks something like this.


(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))     ; compute p'
                   (+ (* q q) (* 2 p q))   ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

So I implemented it in Haskell, just for fun.


fib n = fib' 1 0 0 1 n
  where fib' a b p q 0 = b
        fib' a b p q n | even n =
          fib' a b (p * p + q * q) (q * q + 2 * p * q) (n `div` 2)
        fib' a b p q n =
          fib' (b * q + a * q + a * p) (b * p + a * q) p q (n - 1)

To calculate and print fib(1000000) and fib(10000000) (i.e. the millionth and ten-millionth fibonacci numbers) takes about 3.26 seconds with the Haskell version (when compiled with GHC), and 43.24 seconds with the Scheme version (when interpreted by plt-r5rs, cause I can't figure out how to get it to be r6rs compliant, nor can I figure out how to make the compiler accept r5rs code :( )

Just to have some more fun, I also implemented it iteratively in Python.


def fib(n):
    a = 1
    b = 0
    p = 0
    q = 1

    while n > 0:
        if n % 2 == 0:
            new_p = p * p + q * q
            new_q = q * q + 2 * p * q
            n = n / 2
            p = new_p
            q = new_q
        else:
            new_a = b * q + a * q + a * p
            new_b = b * p + a * q
            n = n - 1
            a = new_a
            b = new_b

    return b

This takes CPython a whopping 1926.49 seconds to calculate the same numbers. Holy fuck, /prog/, maybe you're right about FIOC after all.

Here are the other implementations I've written and their times.

Ruby (995.35 seconds)

def fib(n)
    a = 1
    b = 0
    p = 0
    q = 1

    while n > 0
        if n % 2 == 0:
            new_p = p * p + q * q
            new_q = q * q + 2 * p * q
            n = n / 2
            p = new_p
            q = new_q
        else
            new_a = b * q + a * q + a * p
            new_b = b * p + a * q
            n = n - 1
            a = new_a
            b = new_b
        end
    end
    b
end

C using GMP (3.24 seconds)

void fib(unsigned long n)
{
    mpz_t a, b, p, q, tmp1, tmp2, tmp3;

    mpz_init(a);
    mpz_init(b);
    mpz_init(p);
    mpz_init(q);
    mpz_init(tmp1);
    mpz_init(tmp2);
    mpz_init(tmp3);

    mpz_set_ui(a, 1);
    mpz_set_ui(b, 0);
    mpz_set_ui(p, 0);
    mpz_set_ui(q, 1);

    while(n > 0)
    {
        if(n % 2 == 0)
        {
            // p * p + q * q
            mpz_mul(tmp1, p, p);
            mpz_mul(tmp2, q, q);
            mpz_add(tmp3, tmp1, tmp2);

            // q * q + 2 * p * q;
            mpz_mul_ui(tmp1, p, 2);
            mpz_add(tmp1, tmp1, q);
            mpz_mul(tmp1, tmp1, q);

            mpz_set(p, tmp3);
            mpz_set(q, tmp1);
            n >>= 1;
        }
        else
        {
            // b * q + a * q + a * p;
            mpz_mul(tmp1, b, q);
            mpz_mul(tmp2, a, q);
            mpz_mul(tmp3, a, p);
            mpz_add(tmp3, tmp3, tmp2);
            mpz_add(tmp3, tmp3, tmp1);

            // b * p + a * q;
            mpz_mul(tmp1, b, p);
            mpz_mul(b, a, q);
            mpz_add(b, tmp1, b);

            mpz_set(a, tmp3);
            n--;
        }
    }

    gmp_printf("%Zd\n", b);

    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(p);
    mpz_clear(q);
    mpz_clear(tmp1);
    mpz_clear(tmp2);
    mpz_clear(tmp3);
}

>>39
In case this isn't a troll, it means the
Forced Indentation Of Code

>>41
[spoiler][b][i]FORCED INDENTATION OF THE CODE[/spoiler]

>>43
[u][o][b][i]^BBCODE[sub]FAILURE[/i][/b][/o][/u]

C-C-C-Combo breaker

Back to /b/

>>41
Oh right. Should've remembered that. I guess Haskell doesn't qualify as it has the curlies-and-semicolons mode too.

>>40
it's only an approximation when you're approximating the irrational numbers.

>>45
Haskell: OIOC

FIOC is SAF (Suave as Fuck)

>>48
You're quite mistaken
                       //`'''```,
             o        // LISP   `.,
       ,....OOo.   .c;.',,,.'``.,,.`
    .'      ____.,'.//
   / _____  \___/.'
  | / ||  \\---\|
  ||  ||   \\  ||
  co  co    co co

Are you SUAVE?
Are you a SPACE TOAD?
Are you a SUAVE SPACE TOAD?

If you answered "Yes" to all of the above questions, then SICP (STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS) might be exactly what you've been looking for! Read SICP (STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS) today, and enjoy all the benefits of being a satorized SICP reader. SICP (STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS) is the fastest-growing SMUG LISP WEENIE community with THOUSANDS of members all over the Internet! You, too, can be a part of SICP if you join today! Why not? It's quick and easy - only 3 simple steps!
• First, you have to obtain a copy of SICP and read it. You can read it online using your favorite web browser.
• Second, you need to succeed in founding a Lisp-related meme in /prog/ on world4chan, a popular "programming for trolls" website.
• Third, you need to join the official SICP home /prog/ on world4chan, and apply for membership.
Talk to one of the satorized overlords or any of the other members in the board to sign up today! Upon submitting your application, you will be required to submit links to your successful meme, and you will be tested on your knowledge of STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS. If you are having trouble locating /prog/, the official STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS board, you might be on a wrong web sight. The correct address is >>>/prog/. Follow this link if you are using a http client such as telnet. If you have Sussman points and would like to support SICP, please don't sage this post.

>>49
Precious kopipe.

>>50
I'd know, I wrote it!

>>51
This may have surprised me.

It's quite possibly one of the saddest forms of abuse. Not physical, not emotional, but chemical. Yes, I'm talking about people whose mothers abused them with drugs and alcohol when they were small or even unborn children.
 
Did your mother switch from cheap beer to hard liquor when she found out she was pregnant with you? When you were deeply disturbed by the ending of Return of the Jedi when you were 3 years old, did she let you hit her joint and think it was funny when you choked on the weed smoke? Did your mother, when you were 4 years old, let you snort some lines off her "magic mirror" after you caught her doing the same, and get mad when you became hyper for some reason shortly thereafter?
 
If so, you should visit dis.4chan.org/prog/. Here you can share your stories of your strung-out mother and her attempts to poison you with her narcotics. It's not funny, and it's not cute. It's abuse. And it hurts.

>>1
lol @ GMP
./fib_gmp 10000001  26.74s user 0.38s system 94% cpu 28.763 total
./fib_arprec 10000001  14.49s user 10.11s system 93% cpu 26.373 total

>>38
pow is O(lim_k→∞log^kn)

>>47
Python: FIOC
Sepples: OIOC
Haskell: OFIOC

>>11
def fib(n):
    a, b, p, q = 1, 0, 0, 1
    while n > 0:
        while not(n & 1):
            p, q = p * p + q * q, q * q + 2 * p * q
            n >>= 1
        n -= 1
        a, b = b * q + a * q + a * p, b * p + a * q
    return b
Not actually any faster in python, but if you were doing a lower-level version it would probably shave some time off.

^{Back to /b/, ``GNAA Faggot''}

62 Name: Anonymous 2011-10-08 5:16

|uoɥʇʎd| ( ° o °)

|Lua| ( ^ ~ ^)



function _fib(n)
    local a = 1
    local b = 0
    local p = 0
    local q = 1
    while n > 0 do
        if n % 2 == 0 then
            new_p = p * p + q * q
            new_q = q * q + 2 * p * q
            n = n / 2
            p = new_p
            q = new_q
        else
            new_a = b * q + a * q + a * p
            new_b = b * p + a * q
            n = n - 1
            a = new_a
            b = new_b
        end
    end
    return b
end


function fib(value)
    print(string.format("fib(%d) = %d", value, _fib(value)))
end

print(fib(1000000))
print(fib(10000000))

and if it weren't for that darn bigint bug in luajit, i'm sure this example would be by far the fastest