[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-77@xxxxxxxxxxxxxxxxx*Subject*: FIXNUM (aka Re: Arithmetic issues)*From*: Sebastian Egner <sebastian.egner@xxxxxxxxxxx>*Date*: Wed, 19 Oct 2005 16:27:43 +0200*Delivered-to*: srfi-77@xxxxxxxxxxxxxxxxx

Dear authors of SRFI 77 and readers of the discussion list,

> SRFI 77 issue #5:

> The fixnum operators wrap on overflow, i.e., they perform modular

> arithmetic. For many purposes, it would be better for them to

> signal an error in safe mode. Since the modulus is implementation-

> dependent, portable code cannot generally take advantage of the

> wrapping. Instead, applications are likely to use fixnums simply

> to avoid the overhead of generic arithmetic under the assumption

> that all quantities computed fit in the fixnum range, and feedback

> if this turns out not to be the case will be valuable. On the other

> hand, the wrapping semantics can also be useful, i.e., in the coding

> of a practical implementation of bignums in terms of fixnums. It

> may be that we should consider including two sets of operators:

> fx operators that signal an error upon overflow and wfx operators

> that wrap.

Unfortunately, there are more useful arithmetic models for fixnums:

a) modular (aka wrapping) arithmetics,

b) subrange arithmetics, raising an exception on overflow,

c) exact arithmetics returning several fixnums (sum+carry), and

d) saturated arithmetics (clamping values to range boundaries).

Clearly, a), b) and d) can easily be emulated from c). C) can be

emulated inefficiently from b). Using a) for emulating either b)

or c) is horribly inefficient because the argument range must

essentially be sqrt'ed, losing about an order of magnitude in speed

and a factor of two in storage consumption. D) is also bad for

emulating the other models.

Model d) is used

in signal processing (RGB components, audio samples)---often as

SIMD operations, e.g. Intel MMX has 8-way 8-bit signed or unsigned

saturated arithmetics.

Rationale for dropping a): It is hardly ever useful because the

precision is not a 'porting-time constant', as you acknowledge

yourself (cited above). Wrapping semantics is *not* useful for

implementing bignums---it is too inefficient.

Rationale for dropping d): Too specialized application.

Saturated arithmetic is absolutely essential in fixpoint

signal processing applications, e.g. processing RGB components

or PCM audio samples. Usually the operations are used with SIMD,

e.g. Intel's MMX has an 8-way 8-bit signed or unsigned saturated

addition---and lots of other modes.

Rational for including b): Even if the full tower is present

in a given system, as an implementor you might want to use

FIXNUMs as a basis for implementing BIGNUMs. Now for the workhorse

arithmetics the model of choice is c), but for the rest of the

program (loops, counters, indices into vectors etc.) you might

want to have b). Moreover, FIXNUMs are often useful as efficient

alternatives for exact integer arithmetics, provided they are

used with care (proof obligations are taken seriously).

Concerning the set of operations for b), the rationale suggests

not to be too 'minimal'---which is reflected in the current

design in SRFI 77: full set of comparisons, min/max, etc.

As matter of personal preference, a few minor things I would modify:

* Add the following operations:

fxsign fxnot fxcompare

* Allow multiple arguments in the following operations:

fx+ fx- fx* fxmin fxmax

* Extend the following predicates to test chains:

fx= fx> fx< fx>= fx<=

* Rename the following identifiers:

least-fixnum -> fx-min-value

greatest-fixnum -> fx-max-value

fxbitwise-<op> -> fx<op> for <op> in {and, ior, xor}

fxarithmetic-shift -> fxshift

fxdiv+mod -> fxmod+div

[In fact, 'div+mod' -> 'mod+div' everywhere in the SRFI

in order to have the least significant values come first,

see below.]

* Drop the following operations:

fxzero? fxpositive? fxnegative? fxodd? fxeven?

fxquotient fxmodulo fxremainder fxmodulo+remainder

fxgcd fxlcm

Furthermore I would not distribute the fixnum ops over the

language and a library; I would rather include them all in

the language or leave them out altogether.

Now for c), i.e. arithmetics with carry.

> SRFI 77 issue #4:

> The fixnum operations provide efficient fixnums that "wrap."

> However, they do not give efficient access to the hardware

> facilities for carry and overflow. This would be desirable

> to implement efficient generic arithmetic on fixnums portably.

> On the other hand, there isn't much experience with formulating

> a portable interface to these facilities.

Yes there is. Consult for example pages 3 and 4 of

Henri Cohen: A course in computational algebraic number theory.

Springer, 1993.

Cohen's solution is the following: Add operations for +, -, *,

div+mod, shift, and bfffo (= x -> ceil(log2(M/(2 x)))) where

arguments are in {0..M-1}, where M is a word size modulus,

for example 2^32 or 2^31. The arithmetic operations return the

(mod M)-part of the result and store the (div M)-part of the

result in two global variables called 'overflow' (in {0,1}, for

+ and -) and 'remainder' (in {0..M-1}. for *, div+mod, and shift).

This solution is a favorable compromise between efficiency and

avoiding low level programming. My main concern is the use of

global variables for the carry. Another issue is the use of

an unsigned range, whereas the model b) above (i.e. subrange

arithmetics) is certainly most useful with a range including

negative integers (and there should at least be -1).

Concerning the 'global variables' issue, I propose to

replace it by procedures returning two values, i.e.

sum+carry, difference+borrow, and lsb+msb (for multiplication

and shift). The clumsiness of dealing with multiple values

is largely gone with wider acceptance of LET-VALUES or

SRFI-71's LET, i.e. (LET ((sum carry (+carry x y c))) ...)).

The unsigned vs. signed issue is a little trickier. The primary

purpose for arithmetics with carry is for implementing (fixed

or arbitrary) multiprecision arithmetics, e.g. for implementing

bignums, implementing crypto primitives (say >=1024 bit mod N),

implementing pseudo-random number generators, or emulating floats.

In all these cases, unsigned arithmetics with carry is more useful

than signed arithmetics with carry, as far as the workhorse ops

are concerned. This has two reasons: a) after cascading signed

operations I always have to untie a knot in my head, b) more

seriously the 2-complement interpretation of a word depends on

the wordsize, i.e. #b1000 = -1 as a 4-bit word but = 4 as a 5-bit

word. In the unsigned interpretation the wordsize does not matter.

Sadly, using signed arithmetics for emulating unsigned operations,

i.e. only using the non-negative values of the signed range, is

less efficient itself because the ordinary signed carry word is

not adjacent in valuation to the sum word. (Try adding 3-bit signed

integers, i.e. in {-4..3}, cascading 2-bit integers in {0..3}.)

There are several ways to deal with the signed/unsigned issue:

* Define FIXNUM to be signed, only provide signed arithmetic.

* Define FIXNUM to be unsigned, only provide unsigned arithmetic.

* Define two FIXNUM types for signed and unsigned.

* Define FIXNUM values as having two interpretations: signed/unsigned.

* Define FIXNUM signed, add another type for vectors of unsigned values.

* ...and lots more

In the following proposal a different approach is taken: We define

FIXNUM to be a signed 2-complement range and add operations that

use only the non-negative subrange---but these operations return the

proper carry values for the *subrange*. Limiting to 2-complement

representation and power-of-2 sized range is necessary to make

the ranges fit together properly. This is hardly a restriction.

Moreover, wasting the sign bit is tolerable in terms of speed

and space---and FIXNUM are probably not native hardware integers

anyhow due to one or more tag bits.

In practice, the following proposal represents a reasonable

compromise between efficiency and avoiding low-level programming.

It can be used for implementing multiprecision arithmetics and

implementing efficient bitfield operations in Scheme itself.

1. Define the FIXNUMs to represent w-bit signed 2-complement

integers, i.e. the range is {-2^(w-1)..2^(w-1)-1} for some

global integer constant w (read 'width'), w >= 2, which is

also available as a symbolic constant (e.g. fx-width).

2. Add operations with carry using only the non-negative subrange,

i.e. {0..2^(w-1)-1} of FIXNUM. The behavior of these operations

for negative or non-FIXNUM argument values is left unspecified in

order to allow for 'nearly 1 instruction' implementations. The operations

are not for the casual user, but for the implementor of libraries---so they

fall into the 'all bets are off' category (unlike the model b) operations).

The unsigned operations (define M = 2^(w-1)) are:

(fx-carry+ x y c)

the two values (mod+div (+ x y c) M)

for fixnums x, y in {0..M-1}, c in {0,1}.

Note: Let s0 s1 denote the results of (fx-carry+ x y c).

Then s0 + s1 M = x + y + c, s0 in {0..M-1}, s1 in {0,1}.

(fx-carry- x y c)

the two values (mod+div (- x y c) M)

for fixnums x, y in {0..M-1}, c in {0,1}.

Note: Let s0 s1 denote the results of (fx-carry- x y c).

Then s0 - s1 M = x - y - c, s0 in {0..M-1}, s1 in {0,1}.

(fx-carry* x y c)

compute (mod+div (+ (* x y) c) M)

for fixnums x, y, c in {0..M-1}.

Note: Let p0 p1 denote the results of (fx-carry* x y c).

Then p0 + p1 2^(w-1) = x y + c, p0, p1 in {0..M-1}.

(fx-mod+div x y)

the two values (mod+div x y)

for fixnums x in {0..M-1}, y in {1..M-1}.

Note: Let r q denote the result of (fx-mod+div x y).

Then r + q y = x, r in {0..y-1}, q in {0..M-1}.

(fx-shift-left x0 x1 k)

the two values (mod+div (* (+ x0 (* x1 M)) (expt 2 k)) M)

for fixnums x in {0..M-1} and k in {0..w-2}.

(fx-shift-right x0 x1 k)

the two values (mod+div (div (+ x0 (* x1 M)) (expt 2 k)) M)

for fixnums x0, x1 in {0..M-1} and k in {0..w-2}.

(fx-lsb-index x)

k in {0..w-1} such that the k-th bit is the least significant

bit set in the fixnum x in {1..M-1}, or k = w-1 if x = 0.

(fx-msb-index x)

k in {-1..w-2} such that the k-th bit is the most significant

bit set in the fixnum x in {0..M-1}.

(fx-weight x)

number of bits set for fixnum x in {0..M-1}.

Rationale: carry+/-/*/mod+div are the basic arithmetic operations

on unsigned (w-1)-bit words. The shift operations work on pairs of

words in order to be able to shift long vectors efficiently. The

index finding operations and the weight operation are critical to

implementing vectors of bits. Boolean ops and comparison

are already included as part of the model b).

Combined, the proposals in this email allow for much more efficient

implementations of important data structures (bignums, vectors of

bits, float emulations, many more...), while hardly being more

complicated (remove 11 ops, add 12, introduce some variable arity).

Sebastian.

----

Dr. Sebastian Egner

Senior Scientist

Philips Research Laboratories

Prof. Holstlaan 4 (WDC 1-051, 1st floor, room 51)

5656 AA Eindhoven

The Netherlands

tel: +31 40 27-43166

fax: +31 40 27-44004

email: sebastian.egner@xxxxxxxxxxx

- Prev by Date:
**Re: Arithmetic issues** - Next by Date:
**Re: Arithmetic issues** - Previous by thread:
**Generic Exact Arithmetic** - Next by thread:
**My comments** - Index(es):