sounio-benchmarks/086_multiply_strings.sio at main · Sounio-lang/sounio-benchmarks · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//@ run-pass
// HumanEval 086: Multiply Strings
//
// Multiply two non-negative integers represented as digit arrays
// (most significant digit first, values 0-9). Uses grade-school
// long multiplication. Returns product as digit array.
// Example: [1, 2, 3] * [4, 5, 6] = [5, 6, 0, 8, 8]

struct Buf { data: [i64; 512] }

fn multiply_strings(a: [i64; 256], a_len: i64, b: [i64; 256], b_len: i64, out: &!Buf) -> i64 with Mut, Panic, Div {
    if a_len == 0 || b_len == 0 { return 0 }

    // Product has at most a_len + b_len digits
    let prod_len = a_len + b_len
    var prod = Buf { data: [0; 512] }

    // Multiply each digit of a with each digit of b
    var i: i64 = a_len - 1
    while i >= 0 {
        var j: i64 = b_len - 1
        while j >= 0 {
            let mul = a[i] * b[j]
            let pos1 = i + j
            let pos2 = i + j + 1
            let sum = mul + prod.data[pos2]

            prod.data[pos2] = sum % 10
            prod.data[pos1] = prod.data[pos1] + sum / 10
            j = j - 1
        }
        i = i - 1
    }

    // Skip leading zeros
    var start: i64 = 0
    while start < prod_len - 1 && prod.data[start] == 0 {
        start = start + 1
    }

    // Copy result
    var out_len: i64 = 0
    var k = start
    while k < prod_len {
        out.data[out_len] = prod.data[k]
        out_len = out_len + 1
        k = k + 1
    }

    out_len
}

fn main() -> i64 with IO, Mut, Panic, Div {
    // Test 1: [1, 2, 3] * [4, 5, 6] = 123 * 456 = 56088 -> [5, 6, 0, 8, 8]
    var a1: [i64; 256] = [0; 256]
    a1[0] = 1
    a1[1] = 2
    a1[2] = 3
    var b1: [i64; 256] = [0; 256]
    b1[0] = 4
    b1[1] = 5
    b1[2] = 6
    var o1 = Buf { data: [0; 512] }
    let n1 = multiply_strings(a1, 3, b1, 3, &!o1)
    assert(n1 == 5)
    assert(o1.data[0] == 5)
    assert(o1.data[1] == 6)
    assert(o1.data[2] == 0)
    assert(o1.data[3] == 8)
    assert(o1.data[4] == 8)

    // Test 2: [2] * [3] = 6 -> [6]
    var a2: [i64; 256] = [0; 256]
    a2[0] = 2
    var b2: [i64; 256] = [0; 256]
    b2[0] = 3
    var o2 = Buf { data: [0; 512] }
    let n2 = multiply_strings(a2, 1, b2, 1, &!o2)
    assert(n2 == 1)
    assert(o2.data[0] == 6)

    // Test 3: [9, 9] * [9, 9] = 99 * 99 = 9801 -> [9, 8, 0, 1]
    var a3: [i64; 256] = [0; 256]
    a3[0] = 9
    a3[1] = 9
    var b3: [i64; 256] = [0; 256]
    b3[0] = 9
    b3[1] = 9
    var o3 = Buf { data: [0; 512] }
    let n3 = multiply_strings(a3, 2, b3, 2, &!o3)
    assert(n3 == 4)
    assert(o3.data[0] == 9)
    assert(o3.data[1] == 8)
    assert(o3.data[2] == 0)
    assert(o3.data[3] == 1)

    // Test 4: [0] * [5, 6] = 0 -> [0]
    var a4: [i64; 256] = [0; 256]
    var b4: [i64; 256] = [0; 256]
    b4[0] = 5
    b4[1] = 6
    var o4 = Buf { data: [0; 512] }
    let n4 = multiply_strings(a4, 1, b4, 2, &!o4)
    assert(n4 == 1)
    assert(o4.data[0] == 0)

    // Test 5: [1, 0, 0] * [1, 0] = 100 * 10 = 1000 -> [1, 0, 0, 0]
    var a5: [i64; 256] = [0; 256]
    a5[0] = 1
    var b5: [i64; 256] = [0; 256]
    b5[0] = 1
    b5[1] = 0
    var o5 = Buf { data: [0; 512] }
    let n5 = multiply_strings(a5, 3, b5, 2, &!o5)
    assert(n5 == 4)
    assert(o5.data[0] == 1)
    assert(o5.data[1] == 0)
    assert(o5.data[2] == 0)
    assert(o5.data[3] == 0)

    println("086_multiply_strings: ALL TESTS PASSED")
    0
}