Multiply

Type-level multiplication, one digit of the second operand at a time.

Multiply<A, B> multiplies two non-negative integers and returns the product as a string. Either side may arrive as a string, a number or a bigint, in any combination.

type T0 = Multiply<2, 3> // '6'
type T1 = Multiply<3, '5'> // '15'
type T2 = Multiply<'4', 10> // '40'
type T3 = Multiply<0, 16> // '0'
type T4 = Multiply<'13', '21'> // '273'
type T5 = Multiply<'43423', 321543n> // '13962361689'

This one continues from Sum, and the fastest route to a solution is to keep that addition machinery intact and build one layer on top of it. Nothing here counts to thirteen billion; the answer is assembled digit by digit, exactly as it is on paper.

type T0 = Multiply<2, 3> // '6'
type T1 = Multiply<3, '5'> // '15'
type T2 = Multiply<'4', 10> // '40'
type T3 = Multiply<0, 16> // '0'
type T4 = Multiply<'13', '21'> // '273'
type T5 = Multiply<'43423', 321543n> // '13962361689'

/* _____________ Your Code Here _____________ */

type Multiply<
  A extends string | number | bigint,
  B extends string | number | bigint,
> = string

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'

type cases = [
  Expect<Equal<Multiply<2, 3>, '6'>>,
  Expect<Equal<Multiply<3, '5'>, '15'>>,
  Expect<Equal<Multiply<'4', 10>, '40'>>,
  Expect<Equal<Multiply<0, 16>, '0'>>,
  Expect<Equal<Multiply<'13', '21'>, '273'>>,
  Expect<Equal<Multiply<'43423', 321543n>, '13962361689'>>,
  Expect<Equal<Multiply<9999, 1>, '9999'>>,
  Expect<Equal<Multiply<4325

Detailed Explanation

The solution in full. Everything down to Add is the Sum challenge unchanged; the last four types are the new work:

type Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
 
type Ones = {
  '0': []
  '1': [0]
  '2': [0, 0]
  '3': [0, 0, 0]
  '4': [0, 0, 0, 0]
  '5': [0, 0, 0, 0, 0]
  '6': [0, 0, 0, 0, 0, 0]
  '7': [0, 0, 0, 0, 0, 0, 0]
  '8': [0, 0, 0, 0, 0, 0, 0, 0]
  '9': [0, 0, 0, 0, 0, 0, 0, 0, 0]
}
 
type ColumnTotal<X extends Digit, Y extends Digit, C extends Digit> = [
  ...Ones[X],
  ...Ones[Y],
  ...Ones[C],
]['length']
 
type WrittenDown = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
 
type CarriedOver = ['0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
                    '1', '1', '1', '1', '1', '1', '1', '1', '1', '1']
 
type ColumnIndex = Extract<keyof WrittenDown, number>
 
type Write<X extends Digit, Y extends Digit, C extends Digit> =
  ColumnTotal<X, Y, C> extends infer N extends ColumnIndex
    ? WrittenDown[N]
    : never
 
type Carry<X extends Digit, Y extends Digit, C extends Digit> =
  ColumnTotal<X, Y, C> extends infer N extends ColumnIndex
    ? CarriedOver[N]
    : never
 
type Reverse<S extends string> = S extends `${infer Head}${infer Rest}`
  ? `${Reverse<Rest>}${Head}`
  : ''
 
type AddColumns<
  A extends string,
  B extends string,
  C extends Digit,
  Acc extends string,
> = A extends `${infer X extends Digit}${infer ARest}`
  ? B extends `${infer Y extends Digit}${infer BRest}`
    ? AddColumns<ARest, BRest, Carry<X, Y, C>, `${Write<X, Y, C>}${Acc}`>
    : AddColumns<A, '0', C, Acc>
  : B extends ''
    ? C extends '1'
      ? `1${Acc}`
      : Acc
    : AddColumns<'0', B, C, Acc>
 
type Add<A extends string, B extends string> = AddColumns<
  Reverse<A>,
  Reverse<B>,
  '0',
  ''
>
 
type AddTimes<
  Acc extends string,
  A extends string,
  N extends unknown[],
> = N extends [unknown, ...infer Rest] ? AddTimes<Add<Acc, A>, A, Rest> : Acc
 
type ShiftLeft<S extends string> = S extends '0' ? '0' : `${S}0`
 
type MultiplyColumns<
  A extends string,
  B extends string,
  Acc extends string,
> = B extends `${infer D extends Digit}${infer BRest}`
  ? MultiplyColumns<A, BRest, AddTimes<ShiftLeft<Acc>, A, Ones[D]>>
  : Acc
 
type Multiply<
  A extends string | number | bigint,
  B extends string | number | bigint,
> = MultiplyColumns<`${A}`, `${B}`, '0'>

Everything down to Add is the Sum solution, wrapped so it takes two plain digit strings: it reverses both operands, walks them column by column, totals each column with tuple lengths and splits that total into a written digit and a carried digit through two twenty-element lookup tables. The Sum walkthrough takes it apart line by line. From here on it is a black box with one guarantee worth stating: given two strings without leading zeros, it returns a string without leading zeros.

Horner's method instead of partial products

School multiplication writes one partial product per digit of B, shifts each one, then adds the whole stack. That needs somewhere to keep the stack. The type system prefers a single accumulator, so the solution uses the other arrangement of the same arithmetic: start Acc at '0', read B from the left, and for each digit D set Acc to Acc * 10 + A * D. Every step multiplies what came before by ten and folds in one more digit, so after the last digit Acc is the product.

MultiplyColumns is that loop. The pattern `${infer D extends Digit}${infer BRest}` peels one digit off the front of B, the two adjacent infer placeholders making D match exactly one character while BRest takes the remainder. When B no longer matches, the accumulator is the answer.

Multiplying by ten, and by a single digit

Both operations inside the loop reduce to things that already exist. Multiplying by ten in decimal is appending a character, which is `${S}0`. The one case that needs care is '0', where appending would produce '00' and break the no-leading-zeros guarantee that Add relies on, so ShiftLeft guards it explicitly. Multiplying by a single digit is at most nine additions, so no digit-by-digit product table is needed at all.

AddTimes counts those additions down with a tuple. Ones[D] is already a tuple of length D, and N extends [unknown, ...infer Rest] pops one element per step, adding A to the accumulator each time; when the tuple is empty the recursion stops and the accumulator falls out unchanged. Ones is doing double duty here, as column arithmetic inside Add and as a loop counter outside it.

// Multiply<9, 99>
// D = '9'  shift '0' -> '0'      add '9' nine times   Acc = '81'
// D = '9'  shift '81' -> '810'   add '9' nine times   Acc = '891'
 
// Multiply<315, '100'>, where two of the three digits add nothing
// D = '1'  shift '0' -> '0'      add '315' once       Acc = '315'
// D = '0'  shift '315' -> '3150'                      Acc = '3150'
// D = '0'  shift '3150' -> '31500'                    Acc = '31500'

Three nested loops, each shrinking something, so termination is easy to see: MultiplyColumns removes one character from B per step, AddTimes removes one element from a tuple of length at most nine, and Add is bounded by the length of the longer operand. The total work is proportional to the digits of B times the digits of the product, never to the numbers themselves, which is why an eleven-digit answer costs about as much as a three-digit one.

Edge cases the tests cover

• Multiply<0, 16>, Multiply<728, 0> and Multiply<0, '0'>: Ones['0'] is the empty tuple, so AddTimes returns its accumulator untouched, and every shift of '0' hits the ShiftLeft guard. The accumulator stays '0' instead of growing a tail of zeros.
• Multiply<9999, 1> and Multiply<100_000n, '1'>: one digit, one addition of A onto '0'. The second also shows the input handling, since `${100_000n}` is '100000', without the n suffix and without the underscore separator.
• Multiply<'43423', 321543n> is '13962361689': six digits in B and an eleven-digit product, well past what any tuple-length trick could reach on its own. Multiply<4325234, '39532'> is heavier still, twenty-two additions across five digits, and it is the test that would time out if AddTimes were replaced by adding A to itself B times.
• Multiply<315, '100'>: the trailing zeros of B contribute shifts and no additions, which is how the paper method treats them too.
• Multiply<11n, 13n> and Multiply<'13', '21'>: both operands in the same form. `${A}` normalises all three accepted forms before the arithmetic starts, so nothing below the top-level type has to know which one arrived.

The whole solution is Sum plus a shift and a countdown. Once addition exists as a reusable type, multiplication is a loop around it.