Karatsuba multiplication implemented in TypeScript with in-baked unit tests (from Standford Algorithms course).

karatsuba_multiplication.ts

module Logging {
    let indent = 0;
    let enabled = false;
    
    const indentedMessage = (msg: string) =>
        Array(indent * 2).fill("").join("  ") + msg;

    export const log = (msg: string) => {
        if (enabled)
            console.log(indentedMessage(msg));
    }

    export const enable = () => { enabled = true; }
    export const disable = () => { enabled = false; }

    export const enter = (msg: string) => {
        log(msg);
        indent++;
    }
    export const exit = (msg: string) => {
        indent--;
        log(msg);
    }
}

module Karatsuba {

    const logExitResult = (singleDigits: SingleDigits) => {
        Logging.exit(`return ${JSON.stringify(singleDigits)}`);
        return singleDigits;
    }

    export type SingleDigit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;

    export type SingleDigits = SingleDigit[];

    const isSingleDigit = (num: number): num is SingleDigit =>
        (num >= 0)
        && (num < 10)    
        && ((num - Math.trunc(num)) < 0.001);

    const modTen = (num: number): SingleDigit =>
        (num % 10) as SingleDigit;

    const addZeroDigitsOnLeft = (numberOfZeros: number, digits: SingleDigits): SingleDigits =>
        numberOfZeros < 1 ? digits : [...Array(numberOfZeros).fill(0), ...digits];

    const addZeroDigitsOnRight = (numberOfZeros: number, digits: SingleDigits): SingleDigits =>
        numberOfZeros < 1 ? digits : [...digits, ...Array(numberOfZeros).fill(0)];

    const normalizeLengths = ([left, right]: [SingleDigits, SingleDigits]): [SingleDigits, SingleDigits] => {
        const len = Math.max(left.length, right.length);
        return [
            addZeroDigitsOnLeft(len - left.length, left)
            , addZeroDigitsOnLeft(len - right.length, right)
        ];
    }

    const trimZerosOnLeft = (digits: SingleDigits): SingleDigits => {
        const startingIdx = digits.findIndex(it => it > 0);
        return startingIdx < 0
            ? []
            : digits.slice(startingIdx);
    }

    export const sumSingleDigits = (left: SingleDigits, right: SingleDigits): SingleDigits => {
        const reversedLeft = left.slice().reverse();
        const reversedRight = right.slice().reverse();
        const result: SingleDigits = [];
        let idx = 0;
        let carry: SingleDigit = 0;
        const minLen = Math.min(reversedLeft.length, reversedRight.length);
        while (idx < minLen) {
            pushSummation(reversedLeft[idx], reversedRight[idx]);
            idx++;
        }
        while (idx < reversedLeft.length) 
            pushSummation(reversedLeft[idx++]);
        while (idx < reversedRight.length) 
            pushSummation(reversedRight[idx++]);
        if (carry > 0)
            result.push(carry);
        
        return result.reverse();

        function pushSummation(left: number, right?: number) {
            const summation = ((right === undefined) ? left : left + right) + carry;
            result.push(modTen(summation));
            carry = summation > 9 ? 1 : 0;
        }
    }

    const isSmaller = (left: SingleDigits, right: SingleDigits): boolean => {
        left = trimZerosOnLeft(left.slice());
        right = trimZerosOnLeft(right.slice());
        const leftLen = left.length;
        const rightLen = right.length;
        
        if (leftLen !== rightLen) 
            return (leftLen < rightLen);
        for(let idx = 0; idx < leftLen; idx++) {
            const leftDigit = left[idx];
            const rightDigit = right[idx];
            if (leftDigit !== rightDigit)
                return (leftDigit < rightDigit);
        }

        return false;  
    } 

    export const subtractSingleDigits = (larger: SingleDigits, smaller: SingleDigits): SingleDigits => {
        larger = trimZerosOnLeft(larger.slice());
        smaller = trimZerosOnLeft(smaller.slice());
        if (isSmaller(larger, smaller)) {
            const temp = larger;
            larger = smaller;
            smaller = temp;
        }
            
        const result: SingleDigits = []; 
        larger = larger.reverse();
        smaller = smaller.reverse();
        
        let carry: SingleDigit = 0;   
        for (let idx = 0; idx < smaller.length; idx++) { 
            pushSub(larger[idx], smaller[idx]);
        } 

        for (let idx = smaller.length; idx < larger.length; idx++) 
        { 
            pushSub(larger[idx]);
        } 

        return result.reverse();

        function pushSub(larger: number, smaller?: number) {
            const sub = ((smaller === undefined) ? larger : (larger - smaller)) - carry;
            carry = sub < 0 ? 1 : 0;
            result.push((sub + (carry * 10)) as SingleDigit);  
        }     
    } 

    const multiplySingleDigit = (left: SingleDigit, right: SingleDigit): SingleDigits => {
        const mult = left * right;
        return isSingleDigit(mult)
            ? [mult]
            : [Math.trunc(mult / 10) as SingleDigit, modTen(mult)]; 
    }

    const split = <T>(num: T[]): [T[], T[]] => {
        const firstHalfLength = Math.trunc(num.length / 2);
        return [
            num.slice(0, firstHalfLength),
            num.slice(firstHalfLength)
        ];
    }

    export const multiplySingleDigits = (l: SingleDigits, r: SingleDigits): SingleDigits => {    
        Logging.enter(`multiplySingleDigits(${JSON.stringify(l)}, ${JSON.stringify(r)})`);
        const [left, right] = normalizeLengths([l, r]);
        if ((left.length === 0) || (right.length === 0))
            return logExitResult([]);
        if ((left.length === 1) && (right.length === 1)) 
            return logExitResult(multiplySingleDigit(left[0], right[0]));

        const [leftHigh, leftLow] = split(left);
        const [rightHigh, rightLow] = split(right);

        const highsMultiplied = multiplySingleDigits(leftHigh, rightHigh);
        Logging.log(`highsMultiplied: ${JSON.stringify(highsMultiplied)}`);
        const lowsMultiplied = multiplySingleDigits(leftLow, rightLow);
        Logging.log(`lowsMultiplied: ${JSON.stringify(lowsMultiplied)}`);
        const weirdMultuplied = multiplySingleDigits(sumSingleDigits(leftHigh, leftLow), sumSingleDigits(rightHigh, rightLow))
        Logging.log(`weirdMultuplied: ${JSON.stringify(weirdMultuplied)}`);

        const weirdMinusHighsAndLows = subtractSingleDigits(
            weirdMultuplied
            , sumSingleDigits(highsMultiplied, lowsMultiplied)
        );    
        Logging.log(`weirdMultupliedMinusHighsAndLows: ${JSON.stringify(weirdMinusHighsAndLows)}`);       

        const shiftedHighsMultiplied = addZeroDigitsOnRight(2 * leftLow.length, highsMultiplied);
        Logging.log(`shiftedHighsMultiplied: ${JSON.stringify(shiftedHighsMultiplied)}`);       
        const shiftedWeirdResult = addZeroDigitsOnRight(leftLow.length, weirdMinusHighsAndLows);
        Logging.log(`shiftedWeirdResult: ${JSON.stringify(shiftedWeirdResult)}`);       
            
        return logExitResult(sumSingleDigits(sumSingleDigits(shiftedHighsMultiplied, lowsMultiplied), shiftedWeirdResult));
    }
}

module TestApi {
    export type Scenario = { message: string; pass: boolean; }
    export type Test = { unit: string; scenarios: Scenario[] }

    export function tests(tests: Test[]) {
        const anyFailed = tests.some(test => test.scenarios.some(scenario => !scenario.pass));
        if (anyFailed)
            displayFailures();
        else
            displaySuccesses();
        return;

        function displayFailures() {    
            tests.forEach(test => {
                test.scenarios.filter(it => !it.pass).forEach(scenario => {
                    console.error(`${test.unit}:: ${scenario.message}`);
                });
            });
        }

        function displaySuccesses() {        
            tests.forEach(test => {
                console.log(test.unit);
                test.scenarios.forEach(scenario => {                    
                    console.log(`    ${scenario.message}`);
                });
            });
        }
    }
}

module Tests {

    const isEquivalent = (left: Karatsuba.SingleDigits, right: Karatsuba.SingleDigits): boolean =>
        left.length === right.length
        && left.every((leftItem, idx) => leftItem === right[idx]);
    
    const digitsToStr = (digits: Karatsuba.SingleDigits): string => JSON.stringify(digits);

    type SingleDigitsScenario = [Karatsuba.SingleDigits, Karatsuba.SingleDigits, Karatsuba.SingleDigits];

    function singleDigitsScenarioFn(fn: (left: Karatsuba.SingleDigits, right: Karatsuba.SingleDigits) => Karatsuba.SingleDigits) {
        return (scenario: SingleDigitsScenario): TestApi.Scenario => {
            const result = fn(scenario[0], scenario[1]);
            const matches = isEquivalent(result, scenario[2]);
            return {
                message: matches
                    ? `PASS: (${digitsToStr(scenario[0])}, ${digitsToStr(scenario[1])}) = ${digitsToStr(scenario[2])}`
                    : `FAILED: (${digitsToStr(scenario[0])}, ${digitsToStr(scenario[1])}) = ${digitsToStr(scenario[2])} but encountered ${result}`,
                pass: matches
            };
        }
    }

    function sumSingleDigitsTest(): TestApi.Test {
        return {
            unit: 'sumSingleDigits',
            scenarios: (<SingleDigitsScenario[]>[
                [[0], [0], [0]]
                , [[], [0], [0]]
                , [[0], [], [0]]
                , [[0], [1], [1]]
                , [[8], [1], [9]]
                , [[9], [2], [1, 1]]
                , [[9, 9], [2], [1, 0, 1]]
                , [[9, 9], [9, 9], [1, 9, 8]]
                , [[9, 9, 9], [9, 9], [1, 0, 9, 8]]
                , [[9, 9, 9], [1], [1, 0, 0, 0]]
                , [[9, 0, 0, 9, 9], [9, 3, 0, 0, 9], [1, 8, 3, 1, 0, 8]]
                , [[0, 0, 3], [0, 6, 2, 7], [0, 6, 3, 0]]
            ]).map(singleDigitsScenarioFn(Karatsuba.sumSingleDigits))               
        }        
    }

    function subtractSingleDigitsTest(): TestApi.Test {
        return {
            unit: 'subtractSingleDigits',
            scenarios: (<SingleDigitsScenario[]>[
                [[0], [0], []]
                , [[], [0], []]
                , [[0], [], []]
                , [[1], [0], [1]]
                , [[8], [1], [7]]
                , [[9], [2], [7]]
                , [[1, 3], [7], [0, 6]]
                , [[2, 1], [1, 1], [1, 0]]
                , [[9, 8, 9], [8, 9, 9], [0, 9, 0]]
                , [[9, 0, 0, 9, 9], [3, 2, 1], [8, 9, 7, 7, 8]]                
                , [[7, 2, 0], [0, 6, 3, 0], [0, 9, 0]]
            ]).map(singleDigitsScenarioFn(Karatsuba.subtractSingleDigits))     
        }
    }

    function multiplySingleDigitsTest(): TestApi.Test {
        return {
            unit: 'multiplySingleDigits',
            scenarios: (<SingleDigitsScenario[]>[
                [[0], [0], [0]]
                , [[], [0], [0]]
                , [[0], [], [0]]
                , [[1], [0], [0]]
                , [[0], [1], [0]]
                , [[8], [1], [8]]
                , [[9], [2], [1, 8]]
                , [[3], [9], [2, 7]]
                , [[9], [9], [8, 1]]
                , [[1, 1], [1], [0, 1, 1]]
                , [[1, 1], [9], [0, 9, 9]]
                , [[1, 2], [1, 2], [1, 4, 4]]
                , [[9, 9], [9, 9], [9, 8, 0, 1]]
                , [[1, 9, 9], [2, 4, 4], [0, 4, 8, 5, 5, 6]]
                , [[1, 2, 3, 4], [5, 6, 7, 8], [7, 0, 0, 6, 6, 5, 2]]
                , [[9, 9, 9, 9], [9, 9, 9, 9], [9, 9, 9, 8, 0, 0, 0, 1]]
                , [[1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1]]
                , [[0,1,1,9], [0,3,3,3], [0, 0, 3, 9, 6, 2, 7]]
                , [[0,2,2,4], [0,4,3,3], [0, 0, 9, 6, 9, 9, 2]]
                , [[1, 0, 5, 0, 1, 1, 9], [1, 0, 0, 0, 3, 3, 3], [1, 0, 5, 0, 4, 6, 8, 6, 8, 9, 6, 2, 7]]
            ]).map(singleDigitsScenarioFn(Karatsuba.multiplySingleDigits))     
        }
    }

    alert("Check console for unit test results:");
    TestApi.tests([
        sumSingleDigitsTest()
        , subtractSingleDigitsTest()
        , multiplySingleDigitsTest()
    ]);
}

module Assignment {
    const charToDigit = (s: string): Karatsuba.SingleDigit =>
        Number(s) as Karatsuba.SingleDigit;

    const stringToDigits = (s: string): Karatsuba.SingleDigits =>
        s.split("").map(charToDigit);

    const digitsToString = (d: Karatsuba.SingleDigits): string =>
        d.join("")

    const left = '3141592653589793238462643383279502884197169399375105820974944592';
    const right = '2718281828459045235360287471352662497757247093699959574966967627'
    const result = digitsToString(
        Karatsuba.multiplySingleDigits(
            stringToDigits(left),
            stringToDigits(right)
        )
    );

    alert("Check console for output:");
    console.log(`Multipling ${left} by ${right} = ${result}`);
}