1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
--
-- FIBONACCI.LUA Copyright (c) 2007-08, Asko Kauppi <akauppi@gmail.com>
--
-- Parallel calculation of Fibonacci numbers
--
-- A sample of task splitting like Intel TBB library does.
--
-- References:
-- Intel Threading Building Blocks, 'test all'
-- <http://shareit.intel.com/WikiHome/Articles/111111316>
--
-- Need to say it's 'local' so it can be an upvalue
--
local lanes = require "lanes"
local function WR(str)
io.stderr:write( str.."\n" )
end
-- Threshold for serial calculation (optimal depends on multithreading fixed
-- cost and is system specific)
--
local KNOWN= { [0]=0, 1,1,2,3,5,8,13,21,34,55,89,144 }
-- dummy function so that we don't error when fib() is launched from the master state
lane_threadname = function ( ...)
end
--
-- uint= fib( n_uint )
--
local function fib( n )
lane_threadname( "fib(" .. n .. ")")
local lanes = require"lanes"
--
local sum
local floor= assert(math.floor)
WR( "fib("..n..")" )
if n <= #KNOWN then
sum= KNOWN[n]
else
-- Splits into two; this task remains waiting for the results
--
local gen_f= lanes.gen( "*", fib)
local n1=floor(n/2) +1
local n2=floor(n/2) -1 + n%2
WR( "splitting "..n.." -> "..n1.." "..n2 )
local a= gen_f( n1 )
local b= gen_f( n2 )
-- children running...
local a2= a[1]^2
local b2= b[1]^2
sum = (n%2==1) and a2+b2 or a2-b2
end
io.stderr:write( "fib("..n..") = "..sum.."\n" )
return sum
end
--
-- Right answers from: <http://sonic.net/~douglasi/fibo.htm>
--
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
}
assert( #right==99 )
local N= 80
local res= fib(N)
print( right[N], res )
-- assert( res==right[N] ) -- can't guarantee such a large number will match exactly
|
