Fibonacci Finder - Thought Experiment


#1

This challenge raised a problem with JS that was beautifully addressed already, but before I clutter my mind with the code that did it, I'd like to explore it as a thought experiment.

function add_abc(a, b, c) {
    s = a + b + c;
    c = Math.floor(s / 10);
    s %= 10;
    return [s, c];
}

$a = '273495';                     // random number, not F(x)
$b = '285682';                     // ditto
$c = [];
c = 0;
for (i = $b.length; i > 0; i--) {
    a = +$a[i-1];                  // may be out of range
    b = +$b[i-1];
    console.log(a, b);
    r = add_abc(a, b, c);
    console.log(r);
    s = r[0];
    c = r[1];
    $c.unshift(s.toString(10));
}
$s = $c.join('');

 >    
 5 2
 [ 7, 0 ]
 9 8
 [ 7, 1 ]
 4 6
 [ 1, 1 ]
 3 5
 [ 9, 0 ]
 7 8
 [ 5, 1 ]
 2 2
 [ 5, 0 ]
=> '559177'
 > 273495 + 285682
=> 559177
 >

[Challenge] Fibonacci Finder
#2

I've never seen code that used the '$' as a string indicator. Does this come from a previous language? It actually makes a lot of sense..

I didn't even realize it was a valid character for a variable name, had to look it up.


#3

Yes, the $ character is valid in a variable name, provided there are no DOM confilcts. In other words, jQuery cannot be present unless we alias its $ alias. Not my cup of tea. Just so you know we are getting away with this because jQ is not in use, and hopefully not present in the namespace.

In this instance I wanted to keep the variables a and b tied to their string counterparts so snuck in the extra symbols.

D'uh, jQuery could care less as long we are not conflicting with it, period.

$a = '52461916524905785334311649958648296484733611329035169538240802';  // F(298)
$b = '84885164052257330097714121751630835360966663883732297726369399';  // F(299)

Output

=> '37347080577163115432025771710279131845700275212767467264610201'

Actual

   137347080577163115432025771710279131845700275212767467264610201

No problem, though. We expected this error.


#4

Yup, that last carry. I haven't posted much on these forums, the Fibonacci challenge was my first real interaction here, what is the goal of a "thought experiment"?


#5

Without debugging print statements...

function add_abc(a, b, c) {
    s = a + b + c;
    c = Math.floor(s / 10);
    s %= 10;
    return [s, c];
}
$a = '52461916524905785334311649958648296484733611329035169538240802';
$b = '84885164052257330097714121751630835360966663883732297726369399';
$c = [];
c = 0;
for (i = $b.length; i > 0; i--) {
    a = +$a[i-1];  // may be out of range
    b = +$b[i-1];
    r = add_abc(a, b, c);
    s = r[0];
    c = r[1];
    $c.unshift(s.toString(10));
}
if (c) $c.unshift(c.toString(10));
$s = $c.join('');

To test ideas that lead to a hoped for result. In this case, once the last carry, and length difference (of 1) is handled, this will output an actual Fibonacci number (term) as opposed to the scientific notation float JS is limited to.

To work with the final carry...

if (c) $c.unshift(c.toString(10));
$s = $c.join('');

New output

'137347080577163115432025771710279131845700275212767467264610201'

That leaves the length difference to deal with. We know that error is going to creep in.

The goal of this thought experiment is to produce an engine that will churn out the results we expect at each term.


#6

It follows that any code derived from someone's thought experiment that appears in a challenge submission will be suspect unless it demonstrates significant improvement on the ideas. There has to be some constraint in how far these reach. Participants in a thought experiment would be allowed to submit derivatives, based upon their own contribution. Cheaters are easily spotted. (No innuendto intended. This is a generalization.)


#7

The length difference (of one) addressed…

function add_abc(a, b, c) {
    s = a + b + c;
    c = Math.floor(s / 10);
    s %= 10;
    return [s, c];
}

$a = '84885164052257330097714121751630835360966663883732297726369399';
$b = '137347080577163115432025771710279131845700275212767467264610201';

$c = [];
c = 0;
f = $a.length < $b.length;
for (i = $b.length; i > 0; i--) {
    a = f ? +$a[i-2] : +$a[i-1];
    b = +$b[i-1];
    r = add_abc(a, b, c);
    s = r[0];
    c = r[1];
    if (!isNaN(s)) $c.unshift(s.toString(10));
}
if (c) $c.unshift(c.toString(10));
$s = $c.join('');

IF f, the index i_max does not exist in $a, hence -2., an offset that persists.

How far we have come…

Code
function add_abc(a, b, c) {
    s = a + b + c;
    c = Math.floor(s / 10);
    s %= 10;
    return [s, c];
}

//$a = '52461916524905785334311649958648296484733611329035169538240802';
//$b = '84885164052257330097714121751630835360966663883732297726369399';
$a = '84885164052257330097714121751630835360966663883732297726369399';
$b = '137347080577163115432025771710279131845700275212767467264610201';

function $sum($a, $b) {
    $c = [];
    c = 0;
    f = $a.length < $b.length;
    for (i = $b.length; i > 0; i--) {
        a = f ? +$a[i-2] : +$a[i-1];
        b = +$b[i-1];
        r = add_abc(a, b, c);
        s = r[0];
        c = r[1];
        if (!isNaN(s)) $c.unshift(s.toString(10));
    }
    if (c) $c.unshift(c.toString(10));
    return $c.join('');
}
    

sum = $sum ($a, $b);
/*
function fibonacciFinderN(n) {
    
}
*/

#8

An engine is the heart of a program. The program may have many other functions. but ultimately the draw is this engine. That's the purpose of a thought experiment... To expose the inards of a process.

Ultimately, a thought exeperiment is where we can cement our ideas. Nothing carries forward that doesn't gain traction in this process. It really is the fun part of this discipline.


#9

This solution assumes a length difference of '1' which will suffice for the Fib problem but will fail in the wild. I'm looking at mine again to see how I can handle negative values as readably as possible. Not easy.

As you say, its the fun part of the discipline. This challenge exposed a problem, and so we solve that problem. If we might want to use this again in another context, we need to make it a little more robust.


#10

Wow, subtraction is a LOT harder to work out than addition. My current solution works for the few test cases I threw at it, the only unwanted effect is leading zeros left in the answer when numbers are bigger.

EDIT: Leading 0's fixed.

https://repl.it/JC7K/5

I never really realized how much the logic behind the addition and subtraction of integers relies on the "other" process to work effectively with negatives.


#11

I was looking through the methods of the String.prototype and found this new addition. It's about time!


#12

Just what I need. Too bad it is experimental, still.

A note on my above proposed string adder... It fails.

function fibonacciFinderN(n) {
  var a = '0';
  var b = '1';
  var i = 2;
  var c;
  while (i++ < n) {
    c = $sum(a, b);
    a = b;
    b = c;
    console.log(i,c);
  }
  return c;
}

console.log(fibonacciFinderN(15))

3 '1'
4 '2'
5 '3'
6 '5'
7 '8'
8 '13'
9 '1'
10 '2'
11 '3'
12 '5'
13 '8'
14 '13'
15 '1'
1

I still haven't studied your code (in the challenge or from above) while I struggle with the problem. Right now I'm trying to create a buffer with two arrays of equal length, preloaded with zeros, and the two strings loaded in with right justify. Stuck, just now, but hammering away at it. Should have something working, presently.


#13

function createBuffer(m, n) {
  var buffer = [];
  var size = n.length > m.length ? n.length : m.length;
  buffer.push(new Array(size), new Array(size));
  for (var i = 0; i < size; i++) {
    buffer[0][i] = '0';
    buffer[1][i] = '0';
  }
  $m = m.split('');
  $n = n.split('');
  for (i = size - 1; i >= 0 ; i--) {
    if ($m.length) {
      buffer[0][i] = $m.pop();
    } else {
      break;
    }
  }
  for (i = size - 1; i >= 0 ; i--) {
    if ($n.length) {
      buffer[1][i] = $n.pop();
    } else {
      break;
    }
  }
  return buffer;
}

 > { 
..  a = '2469876'; 
..  b = '357865432'; 
..  createBuffer(a,b); 
..  } 
=> [ [ '0', '0', '2', '4', '6', '9', '8', '7', '6' ],
  [ '3', '5', '7', '8', '6', '5', '4', '3', '2' ] ]

Edit

Refactored...

function createBuffer(m, n) {
  var buffer = [];
  var size = n.length > m.length ? n.length : m.length;
  buffer.push(new Array(size), new Array(size));
  var $m = m.split('');
  var $n = n.split('');
  for (var i = size - 1; i >= 0 ; i--) {
    buffer[0][i] = $m.length ? $m.pop() : '0';
    buffer[1][i] = $n.length ? $n.pop() : '0';
  }
  return buffer;
}

Problem solved (so far)...

function $sum($a, $b) {
    var buffer = createBuffer($a, $b);
    $a = buffer[0].join('');
    $b = buffer[1].join('');
    var a, b, r, s;
    var $c = [];
    var c = 0;
    for (var i = $b.length; i > 0; i--) {
        a = +$a[i-1];
        b = +$b[i-1];
        r = add_abc(a, b, c);
        s = r[0];
        c = r[1];
        if (!isNaN(s)) $c.unshift(s.toString(10));
    }
    if (c) $c.unshift(c.toString(10));
    return $c.join('');
}

Now if I could just remember what my logic was on this line...

if (!isNaN(s)) $c.unshift(s.toString(10));

Forgot what error this fixed. Short term memory is not my strong suit, anymore.


#14

Experimental maybe, but the only incompatibility is with IE and we really need to move on.

Also, be careful with while (i++ < n) as i++ and ++i do slightly different things and its tricky to compare a value while you increment it.

Aside from that, I understand the desire to work with arrays but what do arrays do for you that the native String.prototype methods can't?

EDIT: lol that "if not this string is not a number" is a Shakespearean double negative. Tricky.


#15

Yeah, that is a cheap and dirty shortcut. I do understand prefixed and postfixed, but you raise a good point.

Not sure that I have any real affinity for them, other than that they are mutable and let my slow brain think things through a little easier.

Technically, my buffer above could be replaced with ,

while ($a.length < $b.length) {
    $a = '0' + $a;
}

or some such, on the assumption that $a is shorter than $b.


#16

It had to do with my clunky earlier approach, and now that the strings are equal length it is not needed anymore.

https://repl.it/JE6H/0


#17

Got rid of the buffer and fashioned matched strings, as mentioned earlier.

function matchStrings(m, n) {
  var order = n.length > m.length ? [m, n] : [n, m];
  while (order[0].length < order[1].length) {
    order[0] = '0' + order[0];
  }
  return order;
}

function $sum($a, $b) {
  var strs = matchStrings($a, $b);
  $a = strs[0];
  $b = strs[1];
  // ...

It finds the longer of the two strings and mounts it at the high order index of a return array. The low order index value is then padded with '0''s. The array gets unpacked above.

https://repl.it/JE6H/1


#18

On this particular point, would we not expect the interpreter to evaluate expressions in left to right order, or simulated brackets, first?

i++

is an expression statemet. It would be evaluated before the > expression, would it not? That is the logic I am playing upon.


#19

Your code works and produces the desired results so your use of the i++ is fine. However comparing a value while you're incrementing it makes the code less clear to the next person.

An example, though you already mentioned you understand.
https://repl.it/JFJV/1

So without checking, are you comparing i to n or i + 1 to n?


#20
i + 1 to n

i is incremented first, so is already 3 from the start.

A JS intermediate would read this right away. As the next person is concerned I'm pretty sure it would be that person or someone with the attendant wherewithal.