Collatz

The longest Collatz chain that starts below 30,000: arithmetic and a loop, with no allocation, so it measures the NaNVM runtime's number handling alone. The demo below runs it as JavaScript and as WebAssembly, and shows what each run wrote, how long each took, and the second time as a multiple of the first.

See WASM demos for the other pages.

Demo

The same FunctionalScript program, run two ways: as the JavaScript it already is, and compiled by fjs compile to Rust on the NaNVM runtime, then to WebAssembly. Run calls each in turn and shows what it wrote to standard output and how long the call took.

FunctionalScript source:

/**
 * Finds the start below 30,000 with the longest Collatz chain, then writes
 * a line to standard output saying which it is.
 *
 * A computation on numbers alone, beside the sorting sample, which builds a
 * new array at every step: here nothing is allocated while it searches. A
 * chain's length and its start travel as one number, {@link key}, rather
 * than as a pair.
 *
 * The program is an effect: one `write` command, whose text is encoded to
 * UTF-8 bytes in a bit vector by {@link bytes} here, because `fjs compile`
 * cannot compile `log` and `utf8` yet.
 *
 * @module
 */

/** The search covers the starts from `1` up to, not including, this. */
const limit = 30_000

/** A start's place in a {@link key}: above every start below {@link limit}. */
const scale = 1_048_576

/**
 * How many steps `x` takes to reach `1`, plus `count`: halve an even number,
 * and triple an odd one and add one. Starts below {@link limit} take a few
 * hundred steps at most, so the recursion stays shallow.
 *
 * @type {(x: number, count: number) => number}
 */
const steps = (x, count) => x === 1 ? count : steps(x % 2 === 0 ? x / 2 : 3 * x + 1, count + 1)

/**
 * A start and its chain's length as one number, ordered by the length and
 * then by the start.
 *
 * @type {(start: number) => number}
 */
const key = start => steps(start, 0) * scale + start

/** @type {(a: number, b: number) => number} */
const larger = (a, b) => a > b ? a : b

/**
 * The largest {@link key} of the `n` starts from `lo`, found in halves, so
 * the depth is `log n`.
 *
 * @type {(lo: number, n: number) => number}
 */
const longest = (lo, n) => n === 1 ? key(lo) : larger(longest(lo, n >> 1), longest(lo + (n >> 1), n - (n >> 1)))

/**
 * ASCII text as the bit vector a `write` command carries: the bytes, most
 * significant bit first. An ASCII byte's first bit is `0`, so
 * `fjs/types/bit_vec` spells the vector negated, with that bit set to `1`
 * as the stop bit: the loop starts past it, with `1n`.
 *
 * @type {(text: string) => bigint}
 */
const bytes = text => {
    /** @type {readonly [number, bigint]} */
    let s = [1, 1n]
    while (s[0] < text.length * 8) {
        const i = s[0]
        s = [i + 1, s[1] * 2n + ((text.charCodeAt(i >> 3) >> (7 - i % 8)) & 1 ? 1n : 0n)]
    }
    return -s[1]
}

/** What the program writes, from the largest key. @type {(best: number) => string} */
const report = best =>
    `the longest Collatz chain below ${limit} starts at ${best % scale} and takes ${(best - best % scale) / scale} steps\n`

/**
 * The entry: everything happens in the call, none of it as the module loads,
 * so that the time the page shows holds the search.
 */
export default () => ({
    command: 'write',
    payload: ['stdout', bytes(report(longest(1, limit - 1)))],
    continuation: () => () => ['ok', undefined],
})

Rust that fjs compile writes from it, on the NaNVM runtime:

// @generated by `fjs compile`. Do not edit: recompile the source module instead.

use nanvm_lib::vm::unstable::{bigint_any, f64_any, strict_eq, string_any, string_key};
use nanvm_lib::vm::{Any, Function, IStaticFunction, Nullish, ToAny, ToArray, ToObject};

#[rustfmt::skip]
#[allow(clippy::if_same_then_else)]
pub fn module<A: IStaticFunction>(runtime: Any<A>) -> Result<Any<A>, Any<A>> {
    let _b28: Any<A> = A::static_function(|_self, _args| {
        let _b23: Any<A> = A::static_function(|_self, _args| {
            let mut _b13303: Any<A> = _args.argument(0);
            '_loop23: while Any::<A>::to_boolean({
                let _b13304: Any<A> = _b13303.clone();
                (Any::lt((Any::dot(_b13304.clone(), f64_any(0x0000000000000000)).end())?, ((Any::dot(A::frame(_self)[0].clone(), string_any("length")).end())? * f64_any(0x4020000000000000))?))?
            }) {
                let _b3178: Any<A> = _b13303.clone();
                let _b8: Any<A> = (Any::dot(_b3178.clone(), f64_any(0x0000000000000000)).end())?;
                let _b13305: Any<A> = [(_b8.clone() + f64_any(0x3ff0000000000000))?, (((Any::dot(_b3178.clone(), f64_any(0x3ff0000000000000)).end())? * bigint_any(2))? + (if Any::<A>::to_boolean((((Any::dot(A::frame(_self)[0].clone(), string_any("charCodeAt")).end_call(&A::frame(_self)[1], || Ok([(_b8.clone() >> f64_any(0x4008000000000000))?].to_array().to_any())))? >> (f64_any(0x401c000000000000) - (_b8.clone() % f64_any(0x4020000000000000))?)?)? & f64_any(0x3ff0000000000000))?) { bigint_any(1) } else { bigint_any(0) }))?].to_array().to_any();
                _b13303 = _b13305.clone();
            }
            let _b3179: Any<A> = _b13303;
            Ok(_b3179.clone())
        }, 1, [_args.argument(0), A::frame(_self)[0].clone()].to_array(), Some("($1)=>{let $2=$1;while((()=>{const $3=$2;return $3[0]<$0.length*8;})()){const $4=$2;const $5=$4[0];const $6=[$5+1,$4[1]*2n+($0.charCodeAt($5>>3)>>7-$5%8&1?1n:0n)];$2=$6;}return $2;}")).to_any();
        <Any<A> as core::ops::Neg>::neg((Any::dot((Any::call(_b23.clone(), [[f64_any(0x3ff0000000000000), bigint_any(1)].to_array().to_any()].to_array().to_any()))?, f64_any(0x3ff0000000000000)).end())?)
    }, 1, [runtime.clone()].to_array(), Some("($0)=>{const $1=($2)=>{let $3=$2;while((()=>{const $4=$3;return $4[0]<$0.length*8;})()){const $5=$3;const $6=$5[0];const $7=[$6+1,$5[1]*2n+($0.charCodeAt($6>>3)>>7-$6%8&1?1n:0n)];$3=$7;}return $3;};return -$1([1,1n])[1];}")).to_any();
    let _b43: Any<A> = A::static_function(|_self, _args| { (((((string_any("the longest Collatz chain below ") + (f64_any(0x40dd4c0000000000).to_string().map(|v| v.to_any()))?)? + string_any(" starts at "))? + ((_args.argument(0) % f64_any(0x4130000000000000))?.to_string().map(|v| v.to_any()))?)? + string_any(" and takes "))? + (((_args.argument(0) - (_args.argument(0) % f64_any(0x4130000000000000))?)? / f64_any(0x4130000000000000))?.to_string().map(|v| v.to_any()))?)? + string_any(" steps\n") }, 1, [runtime.clone()].to_array(), Some("($0)=>\"the longest Collatz chain below \"+String(30000)+\" starts at \"+String($0%1048576)+\" and takes \"+String(($0-$0%1048576)/1048576)+\" steps\\n\"")).to_any();
    let _b57: Any<A> = A::static_function(|_self, _args| {
        let _b13306: Any<A> = _args.argument(0);
        let _b13307: Any<A> = _args.argument(1);
        let mut _b13308: Any<A> = _b13306.clone();
        let mut _b13309: Any<A> = _b13307.clone();
        let mut _b13310: Any<A> = Nullish::Undefined.to_any();
        '_loop57: loop {
            let _b7682_21: Any<A> = _b13308.clone();
            let _b7683_22: Any<A> = _b13309.clone();
            if Any::<A>::to_boolean((strict_eq(_b7682_21.clone(), f64_any(0x3ff0000000000000)))?) {
                let _b13311: Any<A> = _b7683_22.clone();
                _b13310 = _b13311.clone();
                break '_loop57;
            } else {
                let _b13312: Any<A> = if Any::<A>::to_boolean((strict_eq((_b7682_21.clone() % f64_any(0x4000000000000000))?, f64_any(0x0000000000000000)))?) { (_b7682_21.clone() / f64_any(0x4000000000000000))? } else { ((f64_any(0x4008000000000000) * _b7682_21.clone())? + f64_any(0x3ff0000000000000))? };
                let _b13313: Any<A> = (_b7683_22.clone() + f64_any(0x3ff0000000000000))?;
                _b13308 = _b13312.clone();
                _b13309 = _b13313.clone();
                continue '_loop57;
            }
        }
        let _b7701: Any<A> = _b13310.clone();
        Ok(_b7701.clone())
    }, 2, [runtime.clone()].to_array(), Some("($0,$1)=>{const $2=$0;const $3=$1;let $4=$2;let $5=$3;let $6=undefined;L0:while(true){const $7=$4;const $8=$5;if($7===1){const $9=$8;$6=$9;break L0;}else{const $10=$7%2===0?$7/2:3*$7+1;const $11=$8+1;$4=$10;$5=$11;continue L0;}}const $12=$6;return $12;}")).to_any();
    let _b63: Any<A> = A::static_function(|_self, _args| { ((Any::call(A::frame(_self)[0].clone(), [_args.argument(0), f64_any(0x0000000000000000)].to_array().to_any()))? * f64_any(0x4130000000000000))? + _args.argument(0) }, 1, [_b57.clone(), runtime.clone()].to_array(), Some("($1)=>$0($1,0)*1048576+$1")).to_any();
    let _b68: Any<A> = A::static_function(|_self, _args| { if Any::<A>::to_boolean((Any::gt(_args.argument(0), _args.argument(1)))?) { Ok(_args.argument(0)) } else { Ok(_args.argument(1)) } }, 2, [runtime.clone()].to_array(), Some("($0,$1)=>$0>$1?$0:$1")).to_any();
    let _b85: Any<A> = A::static_function(|_self, _args| { if Any::<A>::to_boolean((strict_eq(_args.argument(1), f64_any(0x3ff0000000000000)))?) { Any::call(A::frame(_self)[0].clone(), [_args.argument(0)].to_array().to_any()) } else { Any::call(A::frame(_self)[1].clone(), [(Any::call(Function::new(_self.clone()).to_any(), [_args.argument(0), (_args.argument(1) >> f64_any(0x3ff0000000000000))?].to_array().to_any()))?, (Any::call(Function::new(_self.clone()).to_any(), [(_args.argument(0) + (_args.argument(1) >> f64_any(0x3ff0000000000000))?)?, (_args.argument(1) - (_args.argument(1) >> f64_any(0x3ff0000000000000))?)?].to_array().to_any()))?].to_array().to_any()) } }, 2, [_b63.clone(), _b68.clone(), runtime.clone()].to_array(), Some("(function $2($3,$4){return $4===1?$0($3):$1($2($3,$4>>1),$2($3+($4>>1),$4-($4>>1)));})")).to_any();
    Ok([(string_key("default"), A::static_function(|_self, _args| { Ok([(string_key("command"), string_any("write")), (string_key("payload"), [string_any("stdout"), (Any::call(A::frame(_self)[0].clone(), [(Any::call(A::frame(_self)[1].clone(), [(Any::call(A::frame(_self)[2].clone(), [f64_any(0x3ff0000000000000), (f64_any(0x40dd4c0000000000) - f64_any(0x3ff0000000000000))?].to_array().to_any()))?].to_array().to_any()))?].to_array().to_any()))?].to_array().to_any()), (string_key("continuation"), A::static_function(|_self, _args| { Ok(A::static_function(|_self, _args| { Ok([string_any("ok"), Nullish::Undefined.to_any()].to_array().to_any()) }, 0, [A::frame(_self)[0].clone()].to_array(), Some("()=>[\"ok\",undefined]")).to_any()) }, 0, [A::frame(_self)[3].clone()].to_array(), Some("()=>()=>[\"ok\",undefined]")).to_any())].to_object().to_any()) }, 0, [_b28.clone(), _b43.clone(), _b85.clone(), runtime.clone()].to_array(), Some("()=>{return {\"command\":\"write\",\"payload\":[\"stdout\",$0($1($2(1,30000-1)))],\"continuation\":()=>()=>[\"ok\",undefined]};}")).to_any())].to_object().to_any())
}

WebAssembly text (WAT) of the functions compiled from this source, without the NaNVM runtime:

Refused:

File size 546944 exceeds maximum allowed size of 131072 bytes: 'nanvm/demos/wasm/collatz.wat.marked'

Emergent Testing

Idle. Press Run to start the suite.

  • ./proof.f.mjs