#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 09 July 2015
# Website: https://github.com/trizen

# A creative algorithm for arbitrary long integer multiplication.

func long_multiplication(String a, String b) -> String {

    if (a.len < b.len) {
        (a, b) = (b, a)
    }

    '0' ~~ [a, b] && return '0'

    var x = a.reverse.chars.map{.to_n}
    var y = b.reverse.chars.map{.to_n}

    var xlen = x.end
    var ylen = y.end

    var mem = 0
    var map = y.len.of { [] }

    for j in ^y {
        for i in ^x {
            var n = (x[i]*y[j] + mem)
            var(d, m) = n.divmod(10)
            if (i == xlen) {
                map[j] << (m, d)
                mem = 0;
            }
            else {
                map[j] << m
                mem = d
            }
        }

        var n = (ylen - j)
        n > 0 && map[j].append(n.of(0)...)
        var m = (ylen - n)
        m > 0 && map[j].prepend(m.of(0)...)
    }

    var result = []
    var mrange = ^map
    var end    = (xlen + ylen + 2)

    for i in ^end {
        var n = (mrange.sum_by {|j| map[j][i] } + mem)
        (mem, result[result.end+1]) = n.divmod(10)
    }

    result.join.reverse -= /^0+/
}

var r = long_multiplication('37975227936943673922808872755445627854565536638199',
                            '40094690950920881030683735292761468389214899724061')

assert_eq(r, '1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139')

say r
