Class: Fibonacci

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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Object

Define instance methods



389
 
# File 'ext/fibonacci/fibonacci.c', line 389

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

Instance Method Details

#[](n) ⇒ Object

Returns the nth Fibonacci number (iterative calculation).

fib[100]
#=> 354224848179261915075



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
253
254
 
# File 'ext/fibonacci/fibonacci.c', line 224

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 (!fib_is_valid_index(n)) {
    rb_raise(rb_eArgError, "Index must be an integer");
    return Qnil;
  }

  if (fib_is_negative(n)) {
    rb_raise(rb_eArgError, "Index cannot be negative");
    return Qnil;
  }

  if (fib_is_zero(n)) {
    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 using fast matrix-based algorithm.

fib.fast_val(100)
#=> 354224848179261915075

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.



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
 
# File 'ext/fibonacci/fibonacci.c', line 61

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

  if (!fib_is_valid_index(n)) {
    rb_raise(rb_eArgError, "Fibonacci index must be an integer");
    return Qnil;
  }

  if (fib_is_negative(n)) {
    rb_raise(rb_eArgError, "Fibonacci index cannot be negative");
    return Qnil;
  }

  if (fib_is_zero(n)) {
    return ZERO;
  }
  if (rb_equal(n, ONE)) {
    return ONE;
  }
  if (rb_equal(n, TWO)) {
    return ONE;
  }

  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]]



165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
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
 
# File 'ext/fibonacci/fibonacci.c', line 165

static VALUE rb_matrix_form(VALUE self, VALUE n) {
  VALUE base_ary, res_ary, tmp_ary;

  if (!fib_is_valid_index(n)) {
    rb_raise(rb_eArgError, "Matrix index must be an integer");
    return Qnil;
  }

  if (fib_is_negative(n)) {
    rb_raise(rb_eArgError, "Matrix index cannot be negative");
    return Qnil;
  }

  base_ary = rb_ary_new2(ARY_LEN);
  res_ary = rb_ary_new2(ARY_LEN);

  /* base is {{1, 1}, {1, 0}} */
  tmp_ary = rb_ary_new2(ARY_LEN);
  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 Fibonacci number

fib.num_digits(100)
#=> 21



344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
 
# File 'ext/fibonacci/fibonacci.c', line 344

static VALUE num_digits(VALUE self, VALUE n) {
  VALUE phi, num_digits, log_sqrt_5, sqrt_5;

  if (!fib_is_valid_index(n)) {
    rb_raise(rb_eArgError, "Argument must be an integer");
    return Qnil;
  }

  if (fib_is_negative(n)) {
    rb_raise(rb_eArgError, "Argument cannot be negative");
    return Qnil;
  }

  if (fib_is_zero(n)) {
    return ZERO;
  }

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

  if (!RTEST(rb_funcall(n, id_gte, 1, TWO))) {
    return Qnil;
  }

  phi = ONE;
  num_digits = ZERO;
  log_sqrt_5 = ZERO;

  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(5)
#=>    0
       1
       1
       2
       3



303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
 
# File 'ext/fibonacci/fibonacci.c', line 303

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

  if (!fib_is_valid_index(n)) {
    rb_raise(rb_eArgError, "Argument must be an integer");
    return Qnil;
  }

  if (fib_is_negative(n)) {
    rb_raise(rb_eArgError, "Argument 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)) {
      fib_print_value(ZERO);
    } else if (rb_equal(start, ONE)) {
      fib_print_value(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;
      fib_print_value(fib_n);
    }
  }

  return Qnil;
}

#terms(n) ⇒ Object

Returns array with the first n terms of the series

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



264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
 
# File 'ext/fibonacci/fibonacci.c', line 264

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

  if (ary_len < 0) {
    rb_raise(rb_eArgError, "Number of terms cannot be negative");
    return Qnil;
  }

  ary = rb_ary_new2(ary_len);

  for (i = 0; i < ary_len; i++) {
    if (i == 0) {
      rb_ary_store(ary, i, ZERO);
    } else 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;
}