517 - Multiply (tuple arithmetic, no reversing or hard-coding)

[MajorLift]

// handles arbitrarily large numbers
type IntADT = number | string | bigint;
type DigitLUT = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
type Digit = DigitLUT[number];

Solution

type Multiply<
  A extends IntADT,
  B extends IntADT,
  B_TUPLE extends Digit[] = IntToTuple<B>,
  OUTPUT extends Digit[] = [],
  OFFSET extends number = 0,
  B_LSD extends Digit = B_TUPLE extends [] ? '0' : Last<B_TUPLE, Digit>,
  MUL extends IntADT = MultiplyByDigit<A, B_LSD>,
  MUL_LSHIFT extends IntADT = LeftShift<MUL, OFFSET>,
  NEXT extends Digit[] = $sum<never, MUL_LSHIFT, OUTPUT>, 
  IS_ANY_ZERO extends boolean = Any<[Equal<`${A}`, '0'>, Equal<`${B}`, '0'>]>,
  RESULT extends IntADT = IS_ANY_ZERO extends true ? '0'
    : B_TUPLE extends [] 
      ? Join<OUTPUT> 
      : Multiply<A, B, Pop<B_TUPLE>, NEXT, Add<OFFSET, 1>>,
> = RESULT;

Methods

type MultiplyByDigit<
  A extends IntADT, 
  B extends Digit, 
  A_TUPLE extends Digit[] = IntToTuple<A>,
  OUTPUT extends Digit[] = [],
  CARRY_IN extends Digit = '0',
  A_LSD extends Digit = A_TUPLE extends [] ? '0' : Last<A_TUPLE, Digit>,
  MUL extends number = Add<MultiplyDigits<A_LSD, B>, CARRY_IN>,
  CURR extends Digit = LSD<MUL>,
  CARRY_OUT extends Digit = `${MUL}` extends CURR ? '0' : MSD<MUL>,
  NEXT extends Digit[] = Unshift<OUTPUT, CURR>,
  IS_ANY_ZERO extends boolean = Any<[Equal<`${A}`, '0'>, Equal<B, '0'>]>,
  RESULT extends IntADT = IS_ANY_ZERO extends true ? '0'
    : A_TUPLE extends []
      ? CARRY_IN extends '0' ? Join<OUTPUT> : Join<Unshift<OUTPUT, CARRY_IN>>
      : MultiplyByDigit<A, B, Pop<A_TUPLE>, NEXT, CARRY_OUT>
> = RESULT;

type MultiplyDigits<
  A extends Digit, 
  B extends Digit, 
  X extends number = `${A}` extends `${infer X extends number}` ? X : 0,
  Y extends number = `${B}` extends `${infer Y extends number}` ? Y : 0,
  OUTPUT extends unknown[] = [],
  RESULT extends IntADT = Y extends 0 
    ? `${OUTPUT["length"]}` 
    : MultiplyDigits<A, B, X, Subtract<Y, 1>, Concat<OUTPUT, Repeat<X>>>
> = RESULT;

Test cases

type multiply_digits_tests = [
  Expect<Equal<MultiplyDigits<'0', '0'>, '0'>>,  
  Expect<Equal<MultiplyDigits<'0', '9'>, '0'>>,  
  Expect<Equal<MultiplyDigits<'1', '1'>, '1'>>,  
  Expect<Equal<MultiplyDigits<'1', '5'>, '5'>>,  
  Expect<Equal<MultiplyDigits<'5', '1'>, '5'>>,  
  Expect<Equal<MultiplyDigits<'6', '6'>, '36'>>,    
  Expect<Equal<MultiplyDigits<'8', '9'>, '72'>>,    
];

type multiply_by_digit_tests = [
  Expect<Equal<MultiplyByDigit<'0', '0'>, '0'>>,  
  Expect<Equal<MultiplyByDigit<1, '2'>, '2'>>,  
  Expect<Equal<MultiplyByDigit<999, '0'>, '0'>>,  
  Expect<Equal<MultiplyByDigit<'999', '1'>, '999'>>,  
  Expect<Equal<MultiplyByDigit<13, '2'>, '26'>>,  
  Expect<Equal<MultiplyByDigit<999, '9'>, '8991'>>,    
  Expect<Equal<MultiplyByDigit<'1923', '9'>, '17307'>>,    
  Expect<Equal<MultiplyByDigit<123456789, '9'>, '1111111101'>>,  
];

Helpers

type $sum<
  A extends IntADT, 
  B extends IntADT, 
  A_TUPLE extends Digit[] = IntToTuple<A>,
  B_TUPLE extends Digit[] = IntToTuple<B>,
  OUTPUT extends Digit[] = [],
  CARRY_IN extends 0 | 1 = 0,
  A_LSD extends Digit = A_TUPLE extends [] ? '0' : Last<A_TUPLE, Digit>,
  B_LSD extends Digit = B_TUPLE extends [] ? '0' : Last<B_TUPLE, Digit>,
  SUM extends number = Add<CARRY_IN, Add<A_LSD, B_LSD>>,
  CURR extends Digit = LSD<SUM>,
  CARRY_OUT extends 0 | 1 = `${SUM}` extends `${CURR}` ? 0 : 1,
  NEXT extends Digit[] = Unshift<OUTPUT, CURR>,
  RESULT extends Digit[] = All<[Equal<A_TUPLE["length"], 0>, Equal<B_TUPLE["length"], 0>]> extends true
    ? CARRY_IN extends 1 ? Unshift<OUTPUT, '1'> : OUTPUT
    : $sum<A, B, Pop<A_TUPLE>, Pop<B_TUPLE>, NEXT, CARRY_OUT>,
> = RESULT;

/** @returns Digit */
type MSD<N extends IntADT> = 
  `${N}` extends `${infer H extends Digit}${string}` ? H : '0';

/** @returns Digit */
type LSD<N extends IntADT> = 
  `${N}` extends `${string}${infer Rest extends `${infer H}${infer D extends Digit}`}` 
    ? LSD<Rest>
    : `${N}` extends `${infer X extends Digit}` ? X : never;

/** @returns string */
type LeftShift<
  T extends IntADT,
  N extends number = 1,
  OUTPUT extends string = `${T}`,
  NEXT extends string = `${OUTPUT}0`,
  RESULT extends IntADT = N extends 0 ? OUTPUT : LeftShift<T, Subtract<N, 1>, NEXT>,
> = RESULT;

type IntToTuple<
  N extends IntADT,
  OUTPUT extends Digit[] = [],
  CURR extends Digit = `${N}` extends `${infer D extends Digit}${string}` ? D : never,
  NEXT extends string = `${N}` extends `${CURR}${infer Rest}` ? Rest : never,
  RESULT extends Digit[] = N extends '' ? OUTPUT : IntToTuple<NEXT, Push<OUTPUT, CURR>>,
> = RESULT;

type Join<T extends any[], OUTPUT extends string = ``> = 
  T extends [T[0], ...infer Rest]
    ? Join<Rest, `${OUTPUT}${T[0]}`>
    : OUTPUT;

/** @returns number | never */
type Subtract<M extends IntADT, S extends IntADT> = 
  `${M}` extends `${infer A extends number}`
    ? `${S}` extends `${infer B extends number}`
      ? Repeat<A> extends [...Repeat<B>, ...infer Rest] ? Rest["length"] : never
      : A
    : never;

/** @returns number */
type Add<A extends IntADT, B extends IntADT> = 
  `${A}` extends `${infer X extends number}` 
    ? `${B}` extends `${infer Y extends number}`
      ? Concat<Repeat<X>, Repeat<Y>>["length"]
      : X
    : `${B}` extends `${infer Y extends number}`
      ? Y
      : 0;

type All<T extends boolean[]> = 
  T extends [infer B, ...infer Rest extends boolean[]]
    ? B extends true ? All<Rest> : false
    : true;

type Any<T extends boolean[]> = 
  T extends [infer B, ...infer Rest extends boolean[]]
    ? B extends true ? true : Any<Rest>
    : false;

type Shift<T extends unknown[], N extends number = 1> = 
  N extends 0 ? T 
    : T extends [infer _, ...infer Rest]
      ? Shift<Rest, Subtract<N, 1>>
      : [];

type Unshift<T extends unknown[], U extends unknown> = 
  [U, ...T];

type Last<T extends U[], U = any> = 
  T extends [...infer _, infer P extends U] ? P : never;

type Pop<T extends unknown[], N extends number = 1> = 
  N extends 0 ? T
    : T extends [...infer Rest, infer _]
      ? Pop<Rest, Subtract<N, 1>> 
      : [];

type Push<T extends unknown[], U extends unknown> = 
  [...T, U];

type Concat<T extends unknown[], U extends unknown[]> = 
  [...T, ...U];
  
type Repeat<N extends number, T extends unknown = null, M extends T[] = []> = 
  M["length"] extends N ? M : Repeat<N, T, Push<M, T>>;