def Mag.kmul

bend-kit-bignum@0.1.0.0 · bigint.bend:172

import Base

172# Karatsuba while both sides have at least 32 limbs, schoolbook below. f caps
173# the depth; 32 halvings outrun any list that fits in memory.
174def Mag.kmul(+f: Nat, +a: List<&2, U32>, +b: List<&2, U32>) -> List<&2, U32>:
175  match f:
176    case 0n:
177      Mag.school(a, b)
178    case 1n+p:
179      +k = Nat.div(Nat.min(Mag.len(a), Mag.len(b)), 2n)
180      +a0 = Mag.lo(a, k)
181      +a1 = List.drop(&2, U32, a, k)
182      +b0 = Mag.lo(b, k)
183      +b1 = List.drop(&2, U32, b, k)
184      Mag.if(List<&2, U32>, Nat.is_lt(k, 16n),
185        u => Mag.school(a, b),
186        u => Mag.kara(k, Mag.kmul(p, a0, b0), Mag.kmul(p, a1, b1),
187          Mag.kmul(p, Mag.add(a0, a1, 0), Mag.add(b0, b1, 0))))