Class: Fibonacci

Inherits:
Object
  • Object
show all
Defined in:
ext/fibonacci/fibonacci.c

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Object 



23
24
25
26
27
 
# File 'ext/fibonacci/fibonacci.c', line 23

static VALUE
fibonacci_init(VALUE self)
{
    return self;
}

Instance Method Details

#[](n) ⇒ Object

Returns a Fixnum or Bignum.

fib[100]
#=> 354224848179261915075

fib[10]
#=> 55

fib[200]
#=> 280571172992510140037611932413038677189525

The value of nth term is calculated iteratively.

Refer to en.wikipedia.org/wiki/Fibonacci_number#First_identity



273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
 
# File 'ext/fibonacci/fibonacci.c', line 273

static VALUE
rb_iterative_val(VALUE self, VALUE n)
{
    VALUE start = TWO;
    VALUE fib_n_1 = ONE;
    VALUE fib_n_2 = ZERO;
    VALUE fib_n = ZERO;

    if(TYPE(n) != T_FIXNUM)
    {
        rb_raise(rb_eArgError, "Invalid argument for type Fixnum");
        return Qnil;
    }

    if(RTEST(rb_funcall(n, id_lt, 1, ZERO)))
    {
        rb_raise(rb_eArgError, "n cannot be negative");
        return Qnil;
    }

    if(rb_equal(n, ZERO))
    {
      fib_n = ZERO;
    }
    else if(rb_equal(n, ONE))
    {
      fib_n = ONE;
    }
    else
    {
      for(start; RTEST(rb_funcall(start, id_lte, 1, n)); start = rb_funcall(start, id_plus, 1, ONE))
      {
        fib_n = rb_funcall(fib_n_1, id_plus, 1, fib_n_2);
        fib_n_2 = fib_n_1;
        fib_n_1 = fib_n;
      }
    }
    return fib_n;
}

#fast_val(n) ⇒ Object

Returns a Fixnum or Bignum.

fib.fast_val(100)
#=> 354224848179261915075

fib.fast_val(10)
#=> 55

fib.fast_val(200)
#=> 280571172992510140037611932413038677189525

ref: Daisuke Takahashi, A fast algorithm for computing large Fibonacci numbers, Information Processing Letters, Volume 75, Issue 6, 30 November 2000, Pages 243-246, ISSN 0020-0190, 10.1016/S0020-0190(00)00112-5.



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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'ext/fibonacci/fibonacci.c', line 59

static VALUE
rb_fast_val(VALUE self, VALUE n)
{
    VALUE f, l, sign, mask, log2, i, logn, logn_min_1, temp;

    if(TYPE(n) != T_FIXNUM)
    {
        rb_raise(rb_eArgError, "Invalid argument for type Fixnum");
        return Qnil;
    }

    if(RTEST(rb_funcall(n, id_lt, 1, ZERO)))
    {
        rb_raise(rb_eArgError, "n cannot be negative");
        return Qnil;
    }
    else
    {
      if(rb_equal(n, ZERO))
      {
        return ZERO;
      }
      else if(rb_equal(n, ONE))
      {
        return ONE;
      }
      else if(rb_equal(n, TWO))
      {
        return ONE;
      }
      else
      {
        f = ONE;
        l = ONE;
        sign = MINUS_ONE;
        logn = rb_funcall(rb_mMath, id_log2, 1, n);
        logn = rb_funcall(logn, id_floor, 0);
        logn_min_1 = rb_funcall(logn, id_minus, 1, ONE);
        mask = rb_funcall(TWO, id_pow, 1, logn_min_1);
        for(i = ONE; RTEST(rb_funcall(i, id_lte, 1, logn_min_1)); i = rb_funcall(i, id_plus, 1, ONE))
        {
          temp = rb_funcall(f, id_mul, 1, f);
          f = rb_funcall(f, id_plus, 1, l);
          f = rb_funcall(f, id_div, 1, TWO);
          f = rb_funcall(rb_funcall(f, id_mul, 1, f), id_mul, 1, TWO);
          f = rb_funcall(f, id_minus, 1, rb_funcall(temp, id_mul, 1, THREE));
          f = rb_funcall(f, id_minus, 1, rb_funcall(sign, id_mul, 1, TWO));
          l = rb_funcall(temp, id_mul, 1, INT2NUM(5));
          l = rb_funcall(l, id_plus, 1, rb_funcall(TWO, id_mul, 1, sign));
          sign = ONE;
          if(!rb_equal(rb_funcall(n, id_bit_and, 1, mask), ZERO))
          {
            temp = f;
            f = rb_funcall(f, id_plus, 1, l);
            f = rb_funcall(f, id_div, 1, TWO);
            l = rb_funcall(TWO, id_mul, 1, temp);
            l = rb_funcall(l, id_plus, 1, f);
            sign = MINUS_ONE;
          }
          mask = rb_funcall(mask, id_div, 1, TWO);
        }
          if(rb_equal(rb_funcall(n, id_bit_and, 1, mask), ZERO))
          {
            f = rb_funcall(f, id_mul, 1, l);
          }
          else
          {
            f = rb_funcall(f, id_plus, 1, l);
            f = rb_funcall(f, id_div, 1, TWO);
            f = rb_funcall(f, id_mul, 1, l);
            f = rb_funcall(f, id_minus, 1, sign);
          }
      }
    }

    return f;
}

#matrix(n) ⇒ Object

Returns a 2x2 matrix(2-dimensional array).

fib.matrix(10)
#=> [[89, 55], [55, 34]]

fib.matrix(100)
#=> [[573147844013817084101, 354224848179261915075], [354224848179261915075,218922995834555169026]]

arr = fib.matrix(15)
#=> [[987, 610], [610, 377]]

arr[0][1] or arr[1][0] is the value of nth term

Refer to en.wikipedia.org/wiki/Fibonacci_number#Matrix_form



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'ext/fibonacci/fibonacci.c', line 190

static VALUE
rb_matrix_form(VALUE self, VALUE n)
{
    VALUE base_ary;
    VALUE res_ary;
    VALUE tmp_ary;
    long ary_len = 2;

    if(TYPE(n) != T_FIXNUM)
    {
        rb_raise(rb_eArgError, "Invalid argument for type Fixnum");
        return Qnil;
    }

    if(RTEST(rb_funcall(n, id_lt, 1, ZERO)))
    {
        rb_raise(rb_eArgError, "n cannot be negative");
        return Qnil;
    }
    else
    {
        base_ary = rb_ary_new2(ARY_LEN);
        res_ary =  rb_ary_new2(ARY_LEN);
        tmp_ary = rb_ary_new2(ARY_LEN);

        /* base is {{1, 1}, {1, 0}} */
        rb_ary_push(tmp_ary, ONE);
        rb_ary_push(tmp_ary, ONE);
        rb_ary_push(base_ary, tmp_ary);

        tmp_ary = rb_ary_new2(ARY_LEN);
        rb_ary_push(tmp_ary, ONE);
        rb_ary_push(tmp_ary, ZERO);
        rb_ary_push(base_ary, tmp_ary);

        /* res is {{1, 0}, {0, 1}} */
        tmp_ary = rb_ary_new2(ARY_LEN);
        rb_ary_push(tmp_ary, ONE);
        rb_ary_push(tmp_ary, ZERO);
        rb_ary_push(res_ary, tmp_ary);

        tmp_ary = rb_ary_new2(ARY_LEN);
        rb_ary_push(tmp_ary, ZERO);
        rb_ary_push(tmp_ary, ONE);
        rb_ary_push(res_ary, tmp_ary);

        while(!rb_equal(n, ZERO))
        {
            if(rb_equal(rb_funcall(n, id_mod, 1, TWO), ZERO))
            {
                n = rb_funcall(n, id_div, 1, TWO);
                base_ary = rb_matrix_mul(base_ary, base_ary);
            }
            else
            {
                n = rb_funcall(n, id_minus, 1, ONE);
                res_ary = rb_matrix_mul(res_ary, base_ary);
            }
        }
    }

    return res_ary;
}

#num_digits(n) ⇒ Object

Returns the number of digits in the nth term of the series

fib.num_digits(10)
#=> 2

fib.num_digits(100)
#=> 21

Refer to en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding



450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
 
# File 'ext/fibonacci/fibonacci.c', line 450

static VALUE
num_digits(VALUE self, VALUE n)
{
    if(TYPE(n) != T_FIXNUM)
    {
        rb_raise(rb_eArgError, "Invalid argument for type Fixnum");
        return Qnil;
    }

    if(RTEST(rb_funcall(n, id_lt, 1, ZERO)))
    {
        rb_raise(rb_eArgError, "n cannot be negative");
        return Qnil;
    }

    VALUE phi = ONE;
    VALUE num_digits = ZERO;
    VALUE log_sqrt_5 = ZERO;
    VALUE sqrt_5;

    if(rb_equal(n, ZERO))
    {
      return ZERO;
    }

    /*  work around since the value log(phi/sqrt(5)) + 1 = 0.8595026380819693
     *  converting to integer would be zero */
    if(rb_equal(n, ONE))
    {
      return ONE;
    }

    if(RTEST(rb_funcall(n, id_gte, 1, TWO)))
    {
      sqrt_5 = rb_funcall(rb_mMath, id_sqrt, 1, INT2NUM(5));
      log_sqrt_5 = rb_funcall(rb_mMath, id_log10, 1, sqrt_5);

      phi = rb_funcall(phi, id_plus, 1, sqrt_5);
      phi = rb_funcall(phi, id_fdiv, 1, TWO);

      num_digits = rb_funcall(rb_mMath, id_log10, 1, phi);
      num_digits = rb_funcall(num_digits, id_mul, 1, n);
      num_digits = rb_funcall(num_digits, id_minus, 1, log_sqrt_5);

      num_digits = rb_funcall(num_digits, id_floor, 0);
      num_digits = rb_funcall(num_digits, id_plus, 1, ONE);
      num_digits = rb_funcall(num_digits, id_to_i, 0);

      return num_digits;
    }
}

#print(n) ⇒ Object

Prints the first n terms of the series.

fib.print(1)
#=>   0

fib.print(2)
#=>   0
      1
fib.print(5)
#=>    0
       1
       1
       2
       3



389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
 
# File 'ext/fibonacci/fibonacci.c', line 389

static VALUE
print(VALUE self, VALUE n)
{
    VALUE start = ZERO;
    VALUE fib_n_1 = ONE;
    VALUE fib_n_2 = ZERO;
    VALUE fib_n = ZERO;

    if(TYPE(n) != T_FIXNUM)
    {
        rb_raise(rb_eArgError, "Invalid argument for type Fixnum");
        return Qnil;
    }

    if(RTEST(rb_funcall(n, id_lt, 1, ZERO)))
    {
        rb_raise(rb_eArgError, "n cannot be negative");
        return Qnil;
    }

    for(start; RTEST(rb_funcall(start, id_lt, 1, n)); start = rb_funcall(start, id_plus, 1, ONE))
    {
        if(rb_equal(start, ZERO))
        {
            rb_print_num(ZERO);
        }
        else if(rb_equal(start, ONE))
        {
            rb_print_num(ONE);
        }
        else
        {
            fib_n = rb_funcall(fib_n_1, id_plus, 1, fib_n_2);
            fib_n_2 = fib_n_1;
            fib_n_1 = fib_n;
            rb_print_num(fib_n);
        }
    }
    return Qnil;
}

#terms(n) ⇒ Object

Returns a array with the first n terms of the series

fib.terms(5)
#=> [0, 1, 1, 2, 3]

fib.terms(10)
#=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

fib.terms(15)
#=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

fib.terms(0)
#=> []

Refer to en.wikipedia.org/wiki/Fibonacci_number#First_identity



333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
 
# File 'ext/fibonacci/fibonacci.c', line 333

static VALUE
terms(VALUE self, VALUE n)
{
    long ary_len = NUM2LONG(n);
    long i;
    VALUE ary = Qnil;

    if(ary_len < 0)
    {
        rb_raise(rb_eArgError, "num terms cannot be negative");
        return ary;
    }

    ary = rb_ary_new2(ary_len);

    for(i=0; i < ary_len; i++)
    {
        if(i == 0)
        {
            rb_ary_store(ary, i, ZERO);
        }
        if((i > 0))
        {
            if(i <= 2)
            {
                rb_ary_store(ary, i, ONE);
            }
            else
            {
                rb_ary_store(ary, i, rb_funcall(rb_ary_entry(ary, i-1), id_plus, 1, rb_ary_entry(ary, i-2)));
            }
        }
    }
    return ary;
}