4 ms·

Multiplication is generally done in O(n^2) of the number of bits so I'm not sure what you mean to say. Do you mean O(n^2) of the size of the operands?

quickthrower2 4y ago
In Lambda calculus, numbers are encoded using 0 and successor. So 3 = S(S(S(0))) Adding these would be O(N+M) where N and M are the numbers, not the number of bits. Multiplying is O(N*M) where again it is the numbers. 1000*1000 would require a million operations at least. It takes a million operations just to store/read the number million! See: https://en.wikipedia.org/wiki/Church_encoding https://en.wikipedia.org/wiki/Church_encoding Unless this HN submitted implementation doesn't use church encoding. In which case I am wrong.
- atennapel 4y ago
  The page mentions that the implementation has 32 bit signed integers, plus it uses Scott encodings and not Church.
- wrbs 4y ago
  There's nothing about the lambda calculus which forces you to use the church encoding of natural numbers. You could also come up with an encoding based on booleans as bits: {true} = \t f. t {false} = \t f. f then bytes: {0b00001111} = \f. f [false] [false] [false] [false] [true] [true] [true] [true] which you could merge up into larger integers just like real computers. or for one less based on the 8-bits and to keep the infinite range you could just represent integers as lists of binary numbers: {[]} = \c n. n {x::y} = \c n. c x y {0} = [] {1} = [true] {2} = [false, true] (i.e. reversed 0b10) {3} = [true, true] {4} = [false, false, true] which you could imagine using to implement a way more efficient shift-and-add multiply, O(log M * log N)
  - tromp 4y ago
    > {[]} = \c n. n > {x::y} = \c n. c x y Note that Binary Lambda Calculus uses the simpler {x::y} = \c. c x y, which allows you to operate on a list l with l (\head \tail \dummy. non_null_case) null_case
  - quickthrower2 4y ago
    Yeah I made huge assumptions!

quickthrower2 4y ago

In Lambda calculus, numbers are encoded using 0 and successor. So 3 = S(S(S(0))) Adding these would be O(N+M) where N and M are the numbers, not the number of bits. Multiplying is O(N*M) where again it is the numbers. 1000*1000 would require a million operations at least. It takes a million operations just to store/read the number million! See: https://en.wikipedia.org/wiki/Church_encoding https://en.wikipedia.org/wiki/Church_encoding Unless this HN submitted implementation doesn't use church encoding. In which case I am wrong.

atennapel 4y ago
The page mentions that the implementation has 32 bit signed integers, plus it uses Scott encodings and not Church.
wrbs 4y ago
There's nothing about the lambda calculus which forces you to use the church encoding of natural numbers. You could also come up with an encoding based on booleans as bits: {true} = \t f. t {false} = \t f. f then bytes: {0b00001111} = \f. f [false] [false] [false] [false] [true] [true] [true] [true] which you could merge up into larger integers just like real computers. or for one less based on the 8-bits and to keep the infinite range you could just represent integers as lists of binary numbers: {[]} = \c n. n {x::y} = \c n. c x y {0} = [] {1} = [true] {2} = [false, true] (i.e. reversed 0b10) {3} = [true, true] {4} = [false, false, true] which you could imagine using to implement a way more efficient shift-and-add multiply, O(log M * log N)
- tromp 4y ago
  > {[]} = \c n. n > {x::y} = \c n. c x y Note that Binary Lambda Calculus uses the simpler {x::y} = \c. c x y, which allows you to operate on a list l with l (\head \tail \dummy. non_null_case) null_case
- quickthrower2 4y ago
  Yeah I made huge assumptions!