+ { # # -> # } - { # # -> # } * { # # -> # } % { 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:
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.
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.
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 -> publicKeyexcept 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.)
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.