-
Notifications
You must be signed in to change notification settings - Fork 3
/
bjorklund.c
91 lines (82 loc) · 1.65 KB
/
bjorklund.c
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
#include </home/joe/Accents/Accents/bjorklund.h>
/*
Length of output buffer must be at least n.
Length of scratch buffer must be at least 2n.
*/
bool bjorklund(int k, int n, float *output, float *scratch)
{
float *left = scratch;
float *right = scratch + n;
int nleft, nright;
int i, j, m;
// valid values for k and n
if (k > n || n > 100)
return false;
if (k == 0)
{
for (i = 0; i < n; i++)
output[i] = 0;
return true;
}
left[0] = 1;
nleft = 1;
right[0] = 0;
nright = 1;
m = n - k;
while (k + m > 3 && m > 0)
{
if (k < m)
{
m -= k;
// append right to left
for (i = 0, j = nleft; i < nright; i++, j++)
left[j] = right[i];
nleft += nright;
}
else if (m < k)
{
int tmp;
// append right to left
for (i = 0, j = nleft; i < nright; i++, j++)
left[j] = right[i];
// copy original left onto right
for (i = 0; i < nleft; i++)
right[i] = left[i];
// adjust lengths
tmp = nleft;
nleft += nright;
nright = tmp;
// adjust state
tmp = k;
k = m;
m = tmp - m;
}
else
{
// append right to left
for (i = 0, j = nleft; i < nright; i++, j++)
left[j] = right[i];
nleft += nright;
// clear right
nright = 0;
m = 0;
}
}
// construct the output array
// append left k times
j = 0; // length of output
while (k > 0)
{
for (i = 0; i < nleft; i++)
output[j++] = left[i];
k--;
}
// append right m times
while (m > 0)
{
for (i = 0; i < nright; i++)
output[j++] = right[i];
m--;
}
return true;
}