Adding memoization for Fibonacci [Question]

I was trying to make a Fibonacci calculator that was to use an Object Literal as a cache for the results but since the TypeScript configuration does not allow the any type, I am unable to define an Object Literal whose keys are any number from 0 to ~200. I wanted to know if there may be a way around this

Have you tried using a Map<i32,i32>?

So I tried using Map<i32,i32> but then now the compiler brings up different errors concerning the get method in Map. I am using TypeScript v 2.9.

Here's the code I implemented. Maybe you could let me know where I went wrong

let cache: Map<i32, i32> = new Map();
export function fib(num: i32): i32 {
  if (!cache.has(num)) {
    let a: i32 = 0,
      b: i32 = 1,
      tmp: i32;
    for (let i = 0; i < num; i++) {
      // Array destructuting presents an error so I must use a third variable for value swapping
      tmp = a;
      a = b;
      b = tmp + b;
    }
    cache.set(num, a);
  }
  return cache.get(num);
}

Everything works fine. Just see this example
By the way AssemblyScript doesn't depend on TypeScript package.

By the way for huge input numbers you can use analytical fib implementation:

const SQRT5 = Math.sqrt(5.0);
const C1    = Math.log((SQRT5 + 1.0) * 0.5);
const C2    = Math.log((SQRT5 - 1.0) * 0.5);

// result is precise in range [0, 2^53-1]
function fib(n: f64): f64 {
  if (n <= 0) return 0;
  var a = Math.exp(C1 * n);
  var b = Math.exp(C2 * n);
  return Math.round((n & 1 ? a + b : a - b) * (1.0 / SQRT5));
}

Well now it compiles for sure however now the JavaScript code fails to "recognize" the exported code as either functions or objects. This seems to only happen when I have the global cache variable in the code. I am running this code on Node v 10, not on a browser.

The error from the terminal

TypeError: WebAssembly Instantiation: Import #0 module="env" error: module is not an object or function

You JS side should looks like:

WebAssembly.instantiateStreaming(fetch("build/fib.wasm"), {
  env: {
    abort(msg, file, line, column) {
      console.error("abort called at main.ts:" + line + ":" + column);
    }
  },
  console: {
    logi(value) { console.log('logi: ' + value); }
  }
}).then(result => {
  const { fib } = result.instance.exports;
  fib(123);
});

Everything works now. On the browser at least. Thanks.

an Object Literal whose keys are any number from 0 to ~200

Just noticed: From a performance perspective, an array with 200 elements will most likely yield better results:

var cache = new Array<i32>(200);

Now, when accessing a value, you can use value = unchecked(cache[num]), which also disables the usual range check where num is already know to be in range. Note that the array is initialized with all 0 values.

Well the 200 maximum limit was just for an example but that seems like an interesting approach to caching.

I seem to be facing a new problem however. When I try calculating the fibonacci of 50, it returns -298632863 which is because it already exceeds the i32 maximum limit since the fibonacci of 50 is 12,586,269,025 but when I try to use the i64 integers I get this type error

Uncaught (in promise) TypeError: wasm function signature contains illegal type
at WebAssembly.instantiateStreaming.then.result

The code hasn't changed much from my previous implementation

import "allocator/arena";

 let cache: Map<i64, i64> = new Map();
 export function fib(num: i64): i64 {
   if (!cache.has(num)) {
     let a: i64 = 0,
       b: i64 = 1,
       tmp: i64;
     for (let i = 0; i < num; i++) {
       tmp = a;
       a = b;
       b = tmp + b;
     }
     cache.set(num, a);
   }
   return cache.get(num);
 }

It seems you try call fib from JS, but JavaScript doesn't support interop with i64 types yet. So you can do several variants:

use fib(num: f64): f64 instead fib(num: i64): i64. Valid integer range [0, 2^53-1]
Do similar like this. Valid range [0, 2^64-1] but require more efforts:

var __fib_lo: u32 = 0;
var __fib_hi: i32 = 0;
var cache = new Map<i64, i64>();
export function fib(lo: u32, hi: i32): void {
   var num = (<i64>hi << 32) + <i64>lo;
   ...
   var result: i64 = cache.get(num);
   __fib_lo = <u32>(result & 0xFFFFFFFF);
   __fib_hi = <i32>(result >> 32);
}

export function getFibLoResult(): u32 {
  return __fib_lo;
}

export function getFibHiResult(): u32 {
  return __fib_hi;
}

in JS:

import Long from "long";
...
exports.fib(123, 0);
var lo = exports.getFibLoResult();
var hi = exports.getFibHiResult();
var result = new Long(lo, hi);

PS 3. Another one (should be faster):

AS side:

var cache = new Map<i64, i64>();
export function fib(value: f64): f64 {
  var num = reinterpret<i64>(value);
  ...
  return reinterpret<f64>(cache.get(num));
}

JS Side:

import Long from "long";

const F64 = new Float64Array(1);
const I64 = new Uint32Array(F64.buffer);
// helpers
function pack(lo, hi) {
  I64[0] = hi;
  I64[1] = lo;
  return F64[0];
}
function unpack(value) {
  F64[0] = value;
  return { lo: I64[1], hi: I64[0] };
}
...
const { fib } = result.instance.exports;

const { lo, hi } = unpack(fib(pack(123, 0)));
var result = new Long(lo, hi);

These solutions work fine. But the last two seem to need quite some wrapping code obviously.
Seems I might have to be using f64 for all my operations for good measure.

Is the interop a problem with AssemblyScript or browser engines for JavaScript? (If it's AssemblyScript related are there plans to fix it?)

Also, is there provided documentation on how to mitigate such problems? Because your wiki did not have these details.

This interop limitation comes from browsers and WebAssembly spec. Currently there is one big-int proposal which in Stage 3 and also this but not all browsers support BigInt yet.

There is a Binaryen pass that can transform i64 on the boundaries to a pair of i32s as well. To enable it, it should be sufficient to add --runPasses legalize-js-interface to the command line when invoking asc. I believe the respective function then returns the low 32 bits and there is an exported helper that can be called to retrieve the high bits.

Navigation Menu

Repository navigation

Adding memoization for Fibonacci [Question] #162

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Adding memoization for Fibonacci [Question] #162

Description

Activity

dcodeIO commented on Jul 6, 2018

hipstermojo commented on Jul 6, 2018

MaxGraey commented on Jul 6, 2018

MaxGraey commented on Jul 6, 2018

hipstermojo commented on Jul 6, 2018

MaxGraey commented on Jul 6, 2018

hipstermojo commented on Jul 6, 2018

dcodeIO commented on Jul 7, 2018

hipstermojo commented on Jul 9, 2018

MaxGraey commented on Jul 9, 2018

hipstermojo commented on Jul 10, 2018

MaxGraey commented on Jul 10, 2018

dcodeIO commented on Jul 10, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions