Sup Forums Code challenge: Hard mode

Write a program to output the 100,000th Fibonacci number in under 1 seconds.

Note:

Fib(0) = 0
Fib(1) = 1
Fib(2) = 1
Fib(n) = Fib(n-1) + Fib(n-2)

You may use any optimization bar trivial precomputation.

Other urls found in this thread:

play.rust-lang.org/?gist=9e931e46c55b51d9727948b31701dada
gist.github.com/Demonstrandum/4fef6acc9ae3522fea96aeea45ce0cb6
pastebin.com/09UuP6Ea
api.wolframalpha.com/v1/simple?appid=$API_KEY&i=fib(100000)
twitter.com/NSFWRedditVideo

Rust homosexuals need not apply.

#include
#include
#include
#include

int main() {
constexpr uint32_t M = 1000000000, digits = 9, n = 100000;
std::vector x { 0 }, y { 1 } , a { 1 };
for(auto v : {&x, &y, &a})
v->reserve(2400);
for(int k = 0; k < (n - 2); k++) {
std::swap(x, y);
std::swap(y, a);
a.resize(y.size());
uint32_t carry = 0;
auto add = [&carry](uint32_t a, uint32_t b){
uint64_t r = a + b + carry;
carry = (r >= M) ? 1 : 0;
if (carry)
r -= M;
return static_cast(r);
};
for(int i = 0; i < x.size(); i++)
a[i] = add(x[i], y[i]);
for (int i = x.size(); i < y.size(); i++)
a[i] = add(0, y[i]);
if (carry)
a.push_back(carry);
}
auto it = a.rbegin();
std::cout

Ryzen7 1700 Total time:

real 0m0.260s
user 0m0.234s
sys 0m0.000s

Compiled with: -O3 -march=native

>girl
No that's a guy and I want to taste and smell there feet

>He can't into anatomy
Look carefully at the bust and hips

Can't wait for a Rustfaggot to enter the thread with a crate in hand instead of being able to solve the problem with his language's primitive.

We can use our languages standard library, right?

Matlab Master race wins again wins again:
fibonacci(sym(100000))
Elapsed time is 0.058517 seconds.

Pretty slow desu.

Do it in the language primitives rather than an optimized function that probably uses assembler level code.

Is that a fan-art or the author made something about her?

Without displaying the results, finishes in 0.22 seconds.

Weirdly enough when I use gcc 7.2.0 it's slower than gcc 6.3.0... what the hell.

Soon

python -

Man c++ is verbose . Look at it compared to python.

that guy programmed it in C++ like a fucking retard though

>>> timeit.timeit("(matrix([[1,1],[1,0]], dtype='object')**100000)[1,0]", "from numpy import matrix", number=1)
0.02338099479675293

I'd like to see you do better

fn main() {
let instant = std::time::Instant::now();

let mut a = vec!(0);
let mut b = vec!(1);

for _ in 1..100_000 {
add(&mut a, &b);
std::mem::swap(&mut a, &mut b);
}

let d = instant.elapsed();
println!("{:?}\n{} ms", b, (d * 1000).as_secs());
}

fn add(a: &mut Vec, b: &[u64]) {
fn add_carry(a: &mut u64, b: u64, carry: &mut u64) {
*carry += *a + b;
*a = *carry & !(1 >= 63;
}

let extend = b.len() - a.len();
a.extend(std::iter::repeat(0).take(extend));

let mut i = 0;
let mut carry = 0;

while i < b.len() {
add_carry(&mut a[i], b[i], &mut carry);
i += 1;
}

if carry != 0 {
while i < a.len() {
add_carry(&mut a[i], 0, &mut carry);
i += 1;
}
}

if carry != 0 {
a.push(carry);
}
}

play.rust-lang.org/?gist=9e931e46c55b51d9727948b31701dada
Time: 78 ms

gist.github.com/Demonstrandum/4fef6acc9ae3522fea96aeea45ce0cb6

You could just remove all the `BigInt.new(n)` and just leave the `n` for better perform.

Excellent use of the matrix form. numpy's optimizations make it so fast too.

Python:

def fib(n: int) -> int:
if n < 0: return -1
elif n

numpy's optimizations shouldn't really apply since I set the matrix contents to be generic Python objects (because you need BigInts).
It might use exponentiation by squaring though, I'm not sure.

>No code to display the number
Try again.

It does display the number though. OP didn't specify how the number should be displayed.

You overestimate the piece of shit named Matlab dude. If probably use the formula more than anything else and still slow as fuck.

It said output, where's the output then?

Part of the challenge is using a representation that makes display easier, balancing the time consumption of the display code and the calculation. I mean you can print it out in hex but then it's pretty trivial.

>where is the output
look at the last line in the main function. it starts with println!
again: OP didn't state how the number should be output. I did everything OP said I should.

>Part of the challenge is using a representation that makes display easier,
Where is that mentioned anywhere?
And it's 2000 digit number. No accurate representation of the number is easy.

C#:

BigInteger[] dBuf = { 1, 1 };
for (int i = 3; i

>Array of numbers
That's not a fibonnaci number.

>I did everything OP said I should.
Technically correct.

what's wrong with her upper lip?

You can do the same as and roughly get the same performance.

For the naive solution, lets just say that fib(10) takes about 0.5 secs.

There has got to be an easier way.
This Rust one is pretty big too. I thought it was a functional program.

>Array of numbers
By that logic every solution posted so far is not a fibonacci number.
>Technically correct.
You are contradicting yourself.

Really? All that verbosity, constexpr and you are at .26s? Quite underwhelming, isn't it?

import std.stdio, std.bigint;

auto fib(const int n)
{

BigInt next;
for (BigInt i = 0, j = 1, count = 1; count < n; ++count)
{
next = i + j;
i = j;
j = next;
}
return next;
}

void main()
{
writeln(fib(100_000));
}

//benchmarks
$dub build --compiler="ldc" -q --build=release
real 0m0.322s
user 0m0.311s
sys 0m0.010s

//specs
$inxi -CResuming in non X mode: xrandr not found. For package install advice run: inxi --recommendsCPU: Octa core AMD Ryzen 7 1700X Eight-Core (-HT-MCP-) cache: 4096 KB clock speeds: max: 3400 MHz 1: 2200 MHz 2: 2200 MHz 3: 2200 MHz 4: 2200 MHz 5: 2200 MHz 6: 2200 MHz 7: 2200 MHz 8: 2200 MHz 9: 2200 MHz 10: 2200 MHz 11: 2200 MHz 12: 2200 MHz 13: 2200 MHz 14: 2200 MHz 15: 2200 MHz 16: 2200 MHz

>imports bigint
>1700X vs 1700
>Still slower than C++
Activated my almonds, but at least you actually printed it in decimal.

C++ does need a bigint library though.

>std::vector
C/C++ programmers use C/C++ because they rely on GCC's magic to make their poor, mediocre and laughable implementations perform decently

This is ridiculously overcomplicated for what it's trying to achieve.
Good luck getting past interviewers with that...

You could have done this with two arrays only and had better cache locality.

You're not using x[i] once you've added it to y[i], so do the first loop, then propagate the carry in the second loop and extend as necessary.

Can probably speed it up by doing only carry propagation rather than additions in the second loop.

>>imports bigint
And?
X vs 1700
The difference between the two is absolutely negligible.
>>Still slower than C++
I'll take my 0.1s slower code any day, any time over that unreadable trash you just posted. Furthermore, you do realize cannot be any more inefficient, right? It's literally the vanilla "obvious" algorithm.

Not a rustfag but explain yourself

Good points. I'll do it tomorrow morning.

>Good luck getting past interviewers with that...
>Implying I'm not an interviewer.
The goal was speed, not elegance.

I only used vector so I didn't have to keep track of the length of the array. I can probably just zero it all out and add shit unconditionally everywhere. Actually, it's possible that .reserve() isn't working as it should and some allocations are being done, I should do a trace later.

>It's literally the vanilla "obvious" algorithm.
Yeah it was just an entree, I can't wait to see people try their hands at faster ways of computing it but I can't be bothered implementing fast multiplication right now.

#include
#include
#include

#define BIGINT_LEN 5000

int main(int argc, char* argv[]) {
uint64_t *prev, *curr, *next;
uint64_t *temp; // used for swaps later
uint16_t curr_len = 1;
uint64_t bigint_block_max = 1000000000000000000ull;
prev = calloc(BIGINT_LEN, sizeof(uint64_t));
curr = calloc(BIGINT_LEN, sizeof(uint64_t));
next = calloc(BIGINT_LEN, sizeof(uint64_t));

prev[0] = 1;
curr[0] = 0;

for (int n = 100000; n; --n) {
for (int i = 0; i < curr_len; ++i) {
next[i] = prev[i] + curr[i];
if (next[i] >= bigint_block_max) {
// Carry. Safe to alter prev as long as its overwritten later
prev[i+1] += 1;
next[i] -= bigint_block_max;
if (i == curr_len-1) curr_len += 1;
}
}

temp = curr;
curr = next;
next = prev;
prev = temp;
}

for (int i = curr_len-1; i >= 0; --i) {
printf("%llu", curr[i]);
}

return 0;
}


I haven't touched C in a long time, but here's my simple dynamic programming solution. Takes about 300ms to run when compile with -O3. Slower than what I posted in I'm guessing python is using all 64 bits for their bigint and then converting to base 10 at the end (?)

They probably have a hand-assembled way of printing out the bigint at the end

>All those solutions in C/C++
>All of them are slower and more unsafe than my Rust solution
LOL. Is this the power of Sup Forums?

>his Rust solution is much slower than my Python solution
why haven't you committed sudoku already?

Your Rust solution doesn't print out a result and evades the spirit of the exercise. The valid Rust implementation is slower than C++, the fastest current implementation is Python and is technically "safer" than your shitty language.

Have a nice night!

Took 1723ms on my machine. Slower than the C and python solutions I posted earlier. Runtime comparisons require that you run the code on the same or similar systems. Welcome to computers.

>Python is faster
LOOOOOOOOOOOL. LARPers confirmed. You fags probably forgot to turn on otpimizations. Kill yourselves.

>Your Rust solution doesn't print out a result and evades the spirit of the exercise.
My Rust solution does print a result. Just because you don't like the format of it doesn't mean it is invalid.

Calm down.

I'm just going by the number you posted.
The Python code runs in 23ms on an old Thinkpad.
With repetitions it runs in 9ms.

How can I be upset with those trips?

>LARP
>LARP
sure thing kiddo

Just run it yourself if you don't believe me.

What is LARPing? Is that an algorithm?

Is this the python solution?
n = 100000
prev, curr = 1, 0
while n:
curr, prev = curr + prev, curr
n -= 1
print(curr)

this is the more optimized one

pastebin.com/09UuP6Ea

He's talking about the one liner that was posted later: Try it out.

Isn't that a subset of python? That's basically no different than MATLAB

The other one is a "subset of Python" too.
The Rust code is a subset of Rust.

>hurr durr the rust solution is incorrect because it doesn't print the solution in the specific format that OP didn't specify
>hurr durr the python solution that doesn't print anything is fine though XDDDD
thanks for proving me right fags

That's the 99999th fibonacci number

I stayed up and sped up the code a bit by switching to 64-bit words and only using two vectors:

#include
#include
#include
#include

int main() {
constexpr uint64_t M = 1000000000000000000, digits = 18, n = 100000;
std::vector x { 1 }, y { 1 };
x.reserve(1200);
y.reserve(1200);
for(int k = 0; k < (n - 2); k++) {
bool carry = 0;
for(int i = 0; i < x.size(); i++) {
uint64_t r = x[i] + y[i] + carry;
carry = (r >= M) ? 1 : 0;
if (carry)
r -= M;
x[i] = r;
}
if (carry) {
x.push_back(1);
y.push_back(0);
}
std::swap(x, y);
}
auto it = y.rbegin();
std::cout

Calm down.

just prefix a print to it, it doesn't really matter in that case

Okay.
timeit.timeit("print (matrix([[1,1],[1,0]], dtype='object')**100000)[1,0]", "from numpy import matrix", number=1)

How can I be upset with those dubs?

>All that verbosity
>Still slower than python
Have you considered suicide yet?

Shit, you win XDDD

>timeit not defined

Are you guys stupid. optimize the code for clusters or btfo.

haskell strikes again
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
main = print $ fibs !! 100000

250ms on my machine

leave

It's worse than that. He doesn't provide instructions on how to boot the computer.

worse than that. He dosen't even run a DEC mainframe

?
I don't know a single line of python, I pasted that into your repl, doesn't seem to work.

import timeit

Does that print out an integer or a float?

import fibonacci[/import]
The absolute state of python

Both. First the fibonacci number as an integer, then the time as a float

>how dare python have functions for timing code in the standard library
?

Not even using CTFE. Will you able to recover from this?
Don't think so
auto fib(ulong n)
{
import std.bigint : BigInt;
import std.meta : AliasSeq;
import std.typecons : tuple;

BigInt a = 0;
BigInt b = 1;
auto bit = 63;
while (bit > 0)
{
AliasSeq!(a, b) = tuple(a * (2 * b - a), a * a + b * b);


if (n & (BigInt(1)

Fortran...
Program fibtest
Implicit None
Real(Kind=8) :: phi
Real(Kind=8) :: sqrt15

sqrt15 = Sqrt(Real(5,Kind=8))
phi = Real(5d-1,Kind=16)*(1+sqrt15)
Write(*,*) fib(Real(1d5,Kind=8))

Contains
Function fib(n) Result(val)
Implicit None
Real(Kind=8), Intent(In) :: n
Real(Kind=8) :: val
val = (phi**n - ((-phi)**-n) )/sqrt15
End Function fib
End Program fibtest


The only issue with the above code is the fact that the 1000000th Fibonacci number contains 20899 digits... I'm not sure of the value of "Kind" for my "Real"s (floats for you C guys...) I need to be able to calculate the exact value... I don't think anyone in this thread has addressed that issue in their own codes either...

Or in Mathematica...
Fibonacci[100000]


Which yields the number in the attached figure...

Here is a fast version. For reference 10 millionth fib takes ~430ms on my i5.

#include
#include

#define NTH_FIB 100000
#define NO_SLOTS 1000

struct matrix {
mpz_t a0, a1;
mpz_t b0, b1;
};

mpz_t s1, s2, s3;

void temp_init(void)
{
mpz_init(s1);
mpz_init(s2);
mpz_init(s3);
}

size_t pool_free_index;
struct matrix pool[NO_SLOTS];

void pool_init(void)
{
pool_free_index = 0;

for (int i = 0; i < NO_SLOTS; ++i) {
mpz_init(pool[i].a0);
mpz_init(pool[i].a1);
mpz_init(pool[i].b0);
mpz_init(pool[i].b1);
}
}

struct matrix* pool_new(void)
{
if (pool_free_index + 1 >= NO_SLOTS) {
abort();
}

return &pool[pool_free_index++];
}

struct matrix* matrix_mul(struct matrix *m, struct matrix *n)
{
struct matrix *r = pool_new();

mpz_mul(s1, m->a0, n->a0);
mpz_mul(s2, m->a1, n->b0);
mpz_add(s3, s1, s2);
mpz_mul(s1, m->a0, n->a1);
mpz_mul(s2, m->a1, n->b1);
mpz_swap(r->a0, s3);
mpz_add(r->a1, s1, s2);
mpz_mul(s1, m->b0, n->a0);
mpz_mul(s2, m->b1, n->b0);
mpz_add(s3, s1, s2);
mpz_mul(s1, m->b0, n->a1);
mpz_mul(s2, m->b1, n->b1);
mpz_swap(r->b0, s3);
mpz_add(r->b1, s1, s2);

return r;
}

struct matrix* matrix_pow(struct matrix *m, unsigned long p)
{
if (p == 1) {
return m;
}
else if (p % 2) {
return matrix_mul(m, matrix_pow(m, p - 1));
}
else {
struct matrix *r = matrix_pow(m, p / 2);
return matrix_mul(r, r);
}
}

int main(void)
{
pool_init();
temp_init();

struct matrix *n = pool_new();
mpz_set_ui(n->a0, 0);
mpz_set_ui(n->a1, 1);
mpz_set_ui(n->b0, 1);
mpz_set_ui(n->b1, 1);

struct matrix *r = matrix_pow(n, NTH_FIB - 1);
gmp_printf("%Zd\n", r->b1);
}

>Uses BigInts
>Uses different algorithm
>Is homosexual

I mean if I wanted to use a bigint library I can just do this:

// Compile with g++ -march=native -O3 -std=gnu++17 fib -lgmpxx -lgmp -o fib
#include
#include

int main() {
mpz_class x { 1 }, y { 1 };
for (int k = 100000 - 2; k > 0; k--) {
x += y;
std::swap(x, y);
}
std::cout

What dialect of Fortran is that and how do I obtain it?

What exactly do you have against GMP or Bigints?
If you are going to say hurr durr mah external library, don't. Modern languages have moved on, they have standard package management.

It misses the point of the exercise which is to DIY.

Just compared this against the fast numpy version posted previously on 10 million.

/a.out > /dev/null 6.90s user 0.09s system 99% cpu 7.028 total

8.967420367000159

Numpy is pretty nice.

fibonacci is satanic

Shell script

#!/bin/sh
curl api.wolframalpha.com/v1/simple?appid=$API_KEY&i=fib(100000)

Do your own homework.

fib i = snd $ iterate (\(x,y) -> (y,x+y)) (0,1) !! i

real 0m0.331s
user 0m0.313s
sys 0m0.008s


Long live lazily evaluated programs.

you dirty nigger you stole my thread idea and made it harder :O

pssh, nothing personnel

op this is an easy challenge what cpu are you using that cant do this in under a second but just using a loop

>hardmode
I did it in ENTERPRISE QUALITY java on a chromebook using BigInteger and still got it below a second
import java.math.BigInteger;

public class Fibb
{
public static void main(String[] args)
{
BigInteger[] values = new BigInteger[2];
values[0] = BigInteger.ONE;
values[1] = BigInteger.ONE;

BigInteger tmp;
for (int i = 2; i < 100000 ; i++)
{
tmp = values[0];
values[0] = values[1];
values[1] = tmp.add(values[1]);
}
System.out.println(values[1]);
}
}

import "math/big"

func FIb(n int) *big.Int {
if n < 2 {
return big.NewInt(int64(n))
}
a, b := big.NewInt(0), big.NewInt(1)
for i := 2; i /dev/null

real 0m0.051s
user 0m0.033s
sys 0m0.019s

but the golden ratioish equation would be faster and constant time

>arbitrary precision math
>constant time

>arbitraty precision math
I meant fixed float64 or float128, but didn't check if fib(100000) can fit to these