4 ms·
> Using the power of GPUs we are able to calculate F99999999 in only 17 milliseconds on my Consumer GPU FWIW, on my 2020 era laptop, the following: #include
by eesmith 1y ago
> Using the power of GPUs we are able to calculate F99999999 in only 17 milliseconds on my Consumer GPU
FWIW, on my 2020 era laptop, the following:
#include <stdio.h>
int main(void) {
int a = 1, b = 1, c, n = 99999999;
while (--n) {
c = (a+b) % 9837;
a = b;
b = c;
}
printf("%d\n", a);
return 0;
}
takes 330 ms measured as "time a.out".
The problem with Fibonacci is there are algorithmic ways to speed things up. The following (using the method at https://en.wikipedia.org/wiki/Fibonacci_sequence https://en.wikipedia.org/wiki/Fibonacci_sequence to compute Fibonacci numbers recursively in O(log n) arithmetic operations) takes Python 0.1 ms to compute the same value:
import functools
@functools.cache
def F(n):
if n <= 2:
return 1
m = n // 2 # rounds down
if n % 2:
# odd
return (F(m+1)**2 + F(m)**2) % 9837
else:
return ((2*F(m+1) - F(m))*F(m)) % 9837
print(F(99999999))
- amelius 1y agoMaybe a better test is digits of Pi? Or recursive hashing?
- staunton 1y agoA test of what?
- amelius 1y agoTest of your GPU approach/library versus CPU.
- eesmith 1y agoI think the author is more interested in showing how to implement a certain problem using a GPU approach than to test a GPU approach vs. a CPU one. As mentioned, the topic comes from an end-of-chapter problem set on prefix sums, at https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf . A prefix sum cam be implemented using a GPU, as demonstrated. However, using a prefix sum may not be the best way to compute Fibonacci numbers. As demonstrated.
- simon_vtr 1y agoyea, i wrote this blogpost rather to show how to use scan in different ways than the canonical example of calculating prefix sum of a vector shown in introductions on gpu programming.
- qsort 1y agoWell, there's a closed formula right? I wonder if it's faster to carry out the computation in Z[sqrt(5]).
- seanhunter 1y agoYes. Binet’s formula https://mathworld.wolfram.com/BinetsFormula.html https://mathworld.wolfram.com/BinetsFormula.html
- qsort 1y agoYeah, there's a similar formula for all homogeneous linear recurrences if I'm not mistaken, but you can't evaluate it naively with floating point arithmetic. We can view (1 + sqrt(5)) and (1 - sqrt(5)) as elements of Z[sqrt(5)] though. It's probably extremely annoying to write because you have to implement the arithmetic operations in that field, but it wouldn't surprise me if it had faster runtime. Probably Claude can do it? Maybe I'll give it a try later :)
- meindnoch 1y agoGood luck calculating (1+sqrt(5))^n in Z[sqrt(5)].