diff options
| author | Peter Drahoš <drahosp@gmail.com> | 2010-10-01 03:22:32 +0200 |
|---|---|---|
| committer | Peter Drahoš <drahosp@gmail.com> | 2010-10-01 03:22:32 +0200 |
| commit | 89d9c98af1ac352ba4d49d660e61b0853d6e1a86 (patch) | |
| tree | 15c56d2ce66b4ab147171c0f674cdb4a435ff13f /tests/fibonacci.lua | |
| download | lanes-89d9c98af1ac352ba4d49d660e61b0853d6e1a86.tar.gz lanes-89d9c98af1ac352ba4d49d660e61b0853d6e1a86.tar.bz2 lanes-89d9c98af1ac352ba4d49d660e61b0853d6e1a86.zip | |
Import to git
Diffstat (limited to 'tests/fibonacci.lua')
| -rw-r--r-- | tests/fibonacci.lua | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/tests/fibonacci.lua b/tests/fibonacci.lua new file mode 100644 index 0000000..8867e14 --- /dev/null +++ b/tests/fibonacci.lua | |||
| @@ -0,0 +1,75 @@ | |||
| 1 | -- | ||
| 2 | -- FIBONACCI.LUA Copyright (c) 2007-08, Asko Kauppi <akauppi@gmail.com> | ||
| 3 | -- | ||
| 4 | -- Parallel calculation of Fibonacci numbers | ||
| 5 | -- | ||
| 6 | -- A sample of task splitting like Intel TBB library does. | ||
| 7 | -- | ||
| 8 | -- References: | ||
| 9 | -- Intel Threading Building Blocks, 'test all' | ||
| 10 | -- <http://shareit.intel.com/WikiHome/Articles/111111316> | ||
| 11 | -- | ||
| 12 | |||
| 13 | -- Need to say it's 'local' so it can be an upvalue | ||
| 14 | -- | ||
| 15 | local lanes= require "lanes" | ||
| 16 | |||
| 17 | local function WR(str) | ||
| 18 | io.stderr:write( str.."\n" ) | ||
| 19 | end | ||
| 20 | |||
| 21 | -- Threshold for serial calculation (optimal depends on multithreading fixed | ||
| 22 | -- cost and is system specific) | ||
| 23 | -- | ||
| 24 | local KNOWN= { [0]=0, 1,1,2,3,5,8,13,21,34,55,89,144 } | ||
| 25 | |||
| 26 | -- | ||
| 27 | -- uint= fib( n_uint ) | ||
| 28 | -- | ||
| 29 | local function fib( n ) | ||
| 30 | -- | ||
| 31 | local sum | ||
| 32 | local floor= assert(math.floor) | ||
| 33 | |||
| 34 | WR( "fib("..n..")" ) | ||
| 35 | |||
| 36 | if n <= #KNOWN then | ||
| 37 | sum= KNOWN[n] | ||
| 38 | else | ||
| 39 | -- Splits into two; this task remains waiting for the results | ||
| 40 | -- | ||
| 41 | local gen_f= lanes.gen( "io,math,debug", fib ) | ||
| 42 | |||
| 43 | local n1=floor(n/2) +1 | ||
| 44 | local n2=floor(n/2) -1 + n%2 | ||
| 45 | |||
| 46 | WR( "splitting "..n.." -> "..n1.." "..n2 ) | ||
| 47 | |||
| 48 | local a= gen_f( n1 ) | ||
| 49 | local b= gen_f( n2 ) | ||
| 50 | |||
| 51 | -- children running... | ||
| 52 | |||
| 53 | local a2= a[1]^2 | ||
| 54 | local b2= b[1]^2 | ||
| 55 | |||
| 56 | sum = (n%2==1) and a2+b2 or a2-b2 | ||
| 57 | end | ||
| 58 | |||
| 59 | io.stderr:write( "fib("..n..") = "..sum.."\n" ) | ||
| 60 | |||
| 61 | return sum | ||
| 62 | end | ||
| 63 | |||
| 64 | -- | ||
| 65 | -- Right answers from: <http://sonic.net/~douglasi/fibo.htm> | ||
| 66 | -- | ||
| 67 | local right= { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676220, 23416728348467684, 37889062373143900, 61305790721611580, 99194853094755490, 160500643816367070, 259695496911122560, 420196140727489660, 679891637638612200, 1100087778366101900, 1779979416004714000, 2880067194370816000, 4660046610375530000, 7540113804746346000, 12200160415121877000, 19740274219868226000, 31940434634990105000, 51680708854858334000, 83621143489848440000, 135301852344706780000, 218922995834555200000 | ||
| 68 | } | ||
| 69 | assert( #right==99 ) | ||
| 70 | |||
| 71 | local N= 80 | ||
| 72 | local res= fib(N) | ||
| 73 | print( right[N] ) | ||
| 74 | assert( res==right[N] ) | ||
| 75 | |||