Computing Long Sequences of Consecutive Fibonacci Integers with TensorFlow

摘要

Fibonacci numbers appear in numerous engineering and computing applications including population growth models, software engineering, task management, and data structure analysis. This mandates a computationally efficient way for generating a long sequence of successive Fibonacci integers. With the advent of GPU computing and the associated specialized tools, this task is greatly facilitated by harnessing the potential of parallel computing. This work presents two alternative parallel Fibonacci generators implemented in TensorFlow, one based on the well-known recurrence equation generating the Fibonacci sequence and one expressed on inherent linear algebraic properties of Fibonacci numbers. Additionally, the question of using lookup tables in conjunction with spline interpolation or direct computation within a parallel context for the computation of the powers of known quantities is explored. Although both parallel generators outperform the baseline serial implementation in terms of wallclock time and FLOPS, there is no clear winner between them as the results rely on the number of integers generated. Additionally, replacing computations with a lookup table degrades performance, which can be attributed to the frequent access to the shared memory.