### Arithmetic Primitives for Scheme

This development largely obviates this page, but not entirely.
My proposal below could be iced to provide the standard ‘numeric tower’ but probably not as efficiently as many implementations provide it.
See this.
The Scheme standard provides a rich arithmetic universe.
It shuts the programmer away from the binary nature of the platform however.
There are algorithms that exploit well the binary nature of modern computers.
If b is a large integer it is presumably inefficient to invoke a multi-precision division to compute (/ b (expt 2 n)).
Yet it is very efficient for code that has access to the hardware primitives.
Computing the Jacobi symbol in Scheme seems to be a (log n)^{3} algorithm instead of (log n)^{2} when expressed in official Scheme functions.
Not all machines have the same primitives, but the main variation today is whether you have 32 or 64 bit operands at the bottom.

What would access to the raw arithmetic look like in Scheme?
First a query concerning the ‘natural arithmetic word length’.
Next a request for a package of operators on numbers based on a word length specified by the requestor.
Signedness is a problem since some hardware may have a slight preference for signed over unsigned, or conversely.
Some algorithms benefit from signed operands but for initial simplicity I will decree unsigned here for now, for that is the most frequent tool for multi-precision arithmetic.
There are algorithms that use most, but not all of the bits of a binary word in that they weight super digits by a factor smaller than the word size.
I think that that does not bear on the choice of primitives.

I propose that `(pa `*n*) return a list of the primitive functions modulo 2^{n}.
For this note a ‘smint’ is a small integer k, 0≤k<2^{n}.
Operands of the defined operations must be smints, or pairs thereof.
If (a . b) is a pair then f((a . b)) = 2^{n}a + b.
Most of the standard arithmetic operations naturally yield two word answers which we package here as a pair of smints and by ‘pair’ on this page, we a pair of smints.
We speak below as if such a pair represented a number k such that 0≤k<2^{2n} but that is merely a convenient way of specifying the exact semantics of the functions.
Some higher algorithms use these primitives without that interpretation.

- +
`(+ `*a b*) returns a pair representing *a* + *b*.
- −
`(- `*a b*) returns a pair representing 2^{n} + *a* − *b*.
- *
`(* `*a b*) returns a pair representing *ab*.
- /
`(/ (cons `*m n*) *d*) returns a pair of smints (r . q) such that *qd* + r = 2^{n}m + n.

It is required that m and n be smints and that m < d.
- <<
`(<< `*a b*) yields a (c , d) which represents e such that f((c . d)) = 2^{b}a.

It is required that 0 ≤ b < n
- or
`(or a b)` yields a smint which is the bitwise or of a and b.
- and
`(and a b)` yields a smint which is the bitwise and of a and b.

Note that (car (the yield of + or −)) is either 0 or 1.