The Sparrow language

[Timon Gehr via Digitalmars-d]

On 10.04.2016 13:00, Timon Gehr wrote:
> On 10.04.2016 12:01, Lucian Radu Teodorescu wrote:
>> On Wednesday, 6 April 2016 at 21:42:31 UTC, Timon Gehr wrote:
>>> The sum of squares of odd fibonacci numbers example is...
>>> unconvincing. It is inefficient and incorrect.
>>
>> How would you do it?
>> The Fibonacci example isn't very complex, but the idea was to go from
>> really-simple examples to more complex examples.

Forgot to answer this part.

Well, one thing is, Fibonacci numbers grow really quickly, so you'll 
just produce overflow in the cases worth timing. Furthermore, in order 
to compute F_(n+1) you always recompute F_1,...,F_n. The obvious way to 
do it is to have a range of fibonacci numbers with O(1) popFront, filter 
them by parity, and sum up their squares.


However, there is a solution in O(log n) using linear algebra (assuming 
unit costs for arithmetic operations on integers):

F_n = F_(n-1) + F_(n-2)
F_n² = F_(n-1)² + 2 F_(n-1)F_(n-2) + F_(n-2)²
F_n F_(n-1) = F_(n-1)² + F_(n-1) F_(n-2)

I.e., if you know values of (F_n, F_n², F_n F_(n-1)) for a couple of 
subsequent values of n, you can compute them at a larger index by 
applying a linear transformation.

Now just keep enough subsequent values in a vector together with a 
counter to which you add the current odd fibonacci numbers (parity of 
fibonacci numbers follows the 3-periodic pattern 1,1,0,1,1,0,1,1,0,...). 
This vector can be updated from index n to index n+3 by a linear 
transformation. The linear transformation has an associated matrix. Now 
just exponentiate the matrix by exponentiation-by-squaring to transform 
a vector of initial values the correct number of times and read out the 
result from the counter.

If you are able to diagonalize the linear transformation, you'll even 
get a formula in closed form. (I don't have time to do this now, maybe 
later this week.)