Muf Reference - arithmetic and bitwise functions

Go to the first, previous, next, last section, table of contents.

arithmetic and bitwise functions

+          { #   #   -> #   }
-          { #   #   -> #   }
*          { #   #   -> #   }
%          { int int -> int }
/          { int int -> int }
neg        { #       -> #   }
gcd        { int int -> int }
egcd       { int int -> int int int }
lcm        { int int -> int }
ash        { int int -> int }
logand     { int int -> int }
logior     { int int -> int }
lognot     { int     -> int }
logxor     { int int -> int }
1+         { int     -> int }
1-         { int     -> int }
frandom    {         -> flt }
bits       { int     -> int }
trulyRandomFixnum  {         -> int }
trulyRandomInteger { int     -> int }
File: job.t
Status: alpha

Here is a quick table of MUF to C equivalences:

i j %           Return i % j.  Integer only.
m n *           Return m * n.  Any combination of floats and ints.
m n +           Return m + n.  Any combination of floats and ints.
s t +           Append strings s and t.
m n -           Return m - n.  Any combination of floats and ints.
m n /           Return m / n.  Any combination of floats and ints, n != 0.
n   1+          Return n + 1.  Float or int.
n   1-          Return n - 1.  Float or int.
i j logand      Return i & j.  Int only.
i j logior      Return i | j.  Int only.
i j logxor      Return i ^ j.  Int only.
i j ash         Return i << j. Int only.
i   neg         Return     -i. Float or int.
    frandom     Return a pseudorandom() float:  0.0 <= random < 1.0
    trulyRandomFixnum  Return a truly random nonnegative fixnum. (61 bits.)
i   trulyRandomInteger Return a truly random nonnegative i-bit integer.
i   bits        Return number of bits in integer (offset of first 1 bit).

Signed integer values of 62 bits or less are handled as immediate fixnums, and hence are considerably more efficient in space and time. Other integer values are handled as heap-allocated bignums; Currently integer precisions of up to a few thousand bits are supported. Except for efficiency issues, the distinction between fixnums and bignums should not normally be user-visible.

The gcd function returns the Greatest Common Divisor of two integers, using Euclid's algorithm.

Given X,Y the egcd (extended greatest common denominator) function returns GCD,C,D where GCD is the usual greatest common denominator, and where C and D are such that X*C + Y*D == GCD. The extra return values are sometimes useful. In particular, egcd may be used to find modular multiplicative inverses: If X and Y are positive and relatively prime (gcd(X,Y)==1) with X < Y, then the multiplicative inverse of X, mod Y, is A. Here's a sample routine returning the multiplicative inverse else nil:

:  inv { $ $ -> $ }
   -> p  ( The modulus.      )
   -> a  ( Number to invert. )
   a p egcd -> b -> a -> g
   g 1 != if nil return fi ( A and P not relatively prime. )
   a 0 >  if a   return fi
   p a +                   ( Return positive value always. )
;

The lcm function returns the Least Common Multiple of two integers, defined following CommonLisp as abs(a*b) / gcd(a,b).

The log-* functions perform bitwise operations on integers.

The 1+ and 1- functions are no faster than doing 1 + and 1 -, and in fact compile into the same code: Use or non-use of them is a stylistic choice.

Notes:

I dislike the log* names (e.g., and-bits seems more readable and more consistent with our general verb-noun naming convention) and particularly dislike ash for arithmetic shift, but it seems best to stick with the CommonLisp standard here.
The current trulyRandomInteger implementation is a best-effort approach which operates by maintaining an internal bitbuffer into which information from asynchronous events is accumulated: When random bits are requested, a Secure Hash of the bitbuffer is used as a whitening function and the result returned. There is no attempt to guarantee that entropy entered into the bitbuffer exceeds "truly random" bits extracted from the buffer. I expect this implementation to suffice for most intended purposes, in particular passphrase generation and digital signature applications. If not, we can improve the algorithm later without changing the API, and hence without breaking existing dbs in the upgrade.
The generateDiffieHellmanKeyPair function accepts a generator and prime g and p (typically dh:g and dh:p) and returns a public and private Diffie-Hellman key. This is equivalent to doing simply
```
159 trulyRandomInteger -> privateKey
g privateKey p exptmod -> publicKey
```
except that for security the private key is returned as a special #<DiffieHellmanPrivateKey> instead of as an integer. (#<DiffieHellmanPrivateKey> values may not be exported, inspected, or used in ordinary arithmetic operations.)
The generateDiffieHellmanSharedSecret function is equivalent to
publicKey privateKey p exptmod

except that (as security precautions) privateKey is required to be a #<DiffieHellmanPrivateKey> instead of as an integer, and the resulting value is a #<DiffieHellmanSharedSecret> instead of an integer.

Go to the first, previous, next, last section, table of contents.