Operations on var-base numbers (and fast mod N operations)

[VictorTaelin]

In HVM, an interesting way to represent numbers is to use λ-encoded digit-strings of varying bases, parametrized by a list of numbers (a base-list). For example, by using [2,3,5], we represent numbers base 2-3-5:

n = a % 2 + b * 2 % (2 * 3) + c * (2 * 3) % (2 * 3 * 5)

Moreover, since 2 * 3 * 5 = 30, numbers larger than 30 on base 2-3-5 will wrap around. That means operations on them will be mod 30, with no need for a modulus operation. This may help implementing mod N algorithms that fuse, by avoiding calls to mod, which could interrupt fusion.

The base-list can be anything. For example, [100] would give us operations mod 100. But, in turn, each number would use a lot of space, since there are 100 digits. A better idea is to factorize 100 and use [2,2,5,5] instead, which will also give us operations mod 100, but using much less space. Of course, if we use a base-list with identical numbers, say, [2,2,2,2], we'll just have binary numbers, or N-ary, for whatever the N is. Here is the code:

// Applies `f` `n` times to `x`, directly
(Repeat 0 f x) = x
(Repeat n f x) = (f (Repeat (- n 1) f x))

// Given a base-list, applies `f` `n` times to `x`,
// in such a way that is optimized for that base-list
(Apply Nil         n f x) = x
(Apply (Cons b bs) n f x) = (Apply bs (/ n b) λk(Repeat b f k) (Repeat (% n b) f x))

// Given a base-list, applies `f` `n` times to `x`,
// in such a way that is optimized for that base-list
(Times Nil         n f x) = x
(Times (Cons b bs) n f x) = ((TimesGo b b bs n) f x)
  (TimesGo 0 b bs n) = (n λfλx(x))
  (TimesGo i b bs n) = ((TimesGo (- i 1) b bs n) λpλfλx(Times bs p λk(Repeat b f k) (Repeat (- i 1) f x)))

// Given a base, ends a digit-string
(E base) = λend (EGo base end)
  (EGo 0    end) = end
  (EGo base end) = λctr (EGo (- base 1) end)
  
// Given a base, appends `digit` to a digit-string
(D base digit pred) = λend (DGo base digit pred λx(x))
  (DGo 0    n pred ctr) = (ctr pred)
  (DGo base 0 pred ctr) = λctr (DGo (- base 1) (- 0 1) pred ctr)
  (DGo base n pred ctr) = λera (DGo (- base 1) (- n 1) pred ctr)

// Given a base-list, converts a digit-string to a list
(ToList Nil         xs) = Nil
(ToList (Cons b bs) xs) = (ToListGo b bs xs)
  (ToListGo 0 bs xs) = (xs Nil)
  (ToListGo b bs xs) = ((ToListGo (- b 1) bs xs) λp(Cons (- b 1) (ToList bs p)))

// Given a base-list, converts a digit-string to a number
(ToU32 bases xs) = (ToU32Go bases (ToList bases xs) 1)
  (ToU32Go Nil         Nil         m) = 0
  (ToU32Go (Cons b bs) (Cons x xs) m) = (+ (* x m) (ToU32Go bs xs (* m b)))

// Given a base-list, returns the number 0
(Zero Nil        ) = End
(Zero (Cons b bs)) = (D b 0 (Zero bs))

// Giben a base-list, and a u32 `i`, returns the number `n`
(Number bases i) = (Apply bases i λx(Inc bases x) (Zero bases))

// Given a base, applies a function to the predecessor
// (Inj [3] f λeλaλbλc(a pred)) == λeλaλbλc(a (f pred))
(Inj base f xs) = λen (InjGo base f (xs λf(en)))
  (InjGo 0 f xs) = (xs f)
  (InjGo b f xs) = λv (InjGo (- b 1) f (xs λpλf(v (f p))))

// Given a base-list, increments a digit-string
(Inc Nil         xs) = Nil
(Inc (Cons b bs) xs) = λen λn0 (IncMake (- b 1) bs (xs en) λp(n0 (Inc bs p)))
  (IncMake 0 bs xs ic) = (xs ic)
  (IncMake n bs xs ic) = λv (IncMake (- n 1) bs (xs v) ic)

// Given a base-list, increments `b` a total of `a` times
// This is equivalent to addition, and is fast due to fusion
(Add bases a b) = (Times bases a λx(Inc bases x) b)

// Given a base-list, creates an adder for two digit-strings, with carry bits
(AdderCarry Nil         xs) = λys(ys)
(AdderCarry (Cons b bs) xs) = (AdderCarryGo b b bs xs)
  (AdderCarryGo 0 b bs xs) = (xs λys(ys))
  (AdderCarryGo i b bs xs) = ((AdderCarryGo (- i 1) b bs xs) (λxs λys (Repeat (- i 1) λx(Inc (Cons b bs) x) (Inj b (AdderCarry bs xs) ys))))

// Given a base-list, adds two bit-strings, with carry bits
(AddCarry bases xs ys) = ((AdderCarry bases xs) ys)

// FIXME: this is wrong, only works if all bases are the same
(Mul bases xs ys) = (MulGo bases xs λk(Add bases ys k))
  (MulGo Nil         xs add) = End
  (MulGo (Cons b bs) xs add) = (MulDo b b bs xs add)
  (MulDo b 0 bs      xs add) = (xs End)
  (MulDo b i bs      xs add) = ((MulDo b (- i 1) bs xs add) λp(Repeat (- i 1) add (D b 0 (MulGo bs p add))))

(Main x) =
  let bases   = (Cons 2 (Cons 3 (Cons 5 (Cons 7 Nil))))
  let to_list = λx(ToList bases x)
  let to_u32  = λx(ToU32 bases x)
  let times   = λnλfλx(Times bases n f x)
  let apply   = λnλfλx(Apply bases n f x)
  let zero    = (Zero bases)
  let inc     = λx(Inc bases x)
  let add     = λaλb(Add bases a b)
  let addc    = λaλb(AddCarry bases a b)
  let mul_a   = λaλb(Times bases a (add b) zero)  // mul by repeated add by repeated inc
  let mul_b   = λaλb(Times bases a (addc b) zero) // mul by repeated add with carry
  let mul_c   = λaλb(Mul bases a b)               // mul using the incorrect algorithm
  let num     = λi(Number bases i)
  (to_u32 (add (num 123456789) (num 987654321)))

This snippet includes an example of computing 123456789 + 987654321 mod 210, and it efficiently outputs 60, no call to mod is needed. Problems:

• How do we implement mul and exp efficiently? The code above has mul, but is wrong (see the FIXME).

• Given a function f(x) = a^x mod N, what is the optimal algorithm for finding the period?