Re: test

hi,

i got this list so we could also archive stuff and it is easier to get
others to join or lurk than each of us having a set of email
addresses. i also didn't want to use the main internals list for this
work.  we seem to have 4 list members which is fine for now. my friend
mike mckernan hasn't joined (he is not a perl6 guy) but i invited him as
he is my bcd math expert and retaught me the excess-3 and correct 6
methods. i first learned them from him 15 years ago. :)

anyhow, i haven't done much very recently due to other stuff on my
plate. here is what i have so far.

we have a basic design for the format of decimal numbers. my goal is to
support both integers and float and decimals with fractions all in one
structure. the reason i chose bcd is for convenience in converting
to/from strings and for decimal accuracy and because we can support the
aforementioned decimal forms in one type. the other bignum designs i
have researched support only one of those forms for each underlying
type. i expect decent but not blazing speed out of this but if you want
speed, you shouldn't be using perl. :)

here is the data structure:

typedef struct bignum {

	BIGNUM_WORD	*buff ;
	int	int_words ;
	int	int_digits ;
	int	frac_words ;
	int	frac_digits ;
	int	buff_words ;
	int	is_neg ;
	int	expon ;

} BIGNUM ;


it needs to have a buf_size field added after the buff to be compatible
with what dan wants in all allocated structures which have private
buffers. the buffer pointer and then size are the first 2 elements.

the buffer is an array of machine words. there are macros that define
the number of nibbles (bcd digits) per word. buff_words is the number of
words allocated in the buffer (i may move it earlier in te struct for
consistancy). int_words is how many words are in the integer part of the
number. int_digits is the actual number of integer digits in the
number. frac_* are similar for the fraction part. is_neg is a negative
flag. expon is the signed decimal exponent

the number is stored in the buffer with the decimal point always between
two words. this means we can do additions/subtractions with only munging
pointers to do the decimal alignments.

the exponent is effectively how many decimal digits we don't store but
are before or after the decimal point. so we can have a number with a
precision of only 16 digits but an exponent of 80 and it will take up
only 2 (32 bit) words of storage.

so when a number is created it will have a maximum precision (we need to
add this field). this is maximum number of digits the number can
store. it can be changed by extending the number. we may have a flags
for that so some numbers will extend forever. normal numbers will lose
data if they have more digits than their precision allows. scaling will
be handled by a combination of munging the int/frac struct members and
the exponent. as i said before the exponent will always reflect how many
0 digits are before/after the decimal point. you effectively have to
decimal shift the precision number of digits away from the decimal point
to get the exponent into play.

bignums are stored in sign/magnitude format. the nnmber in the buffer is
always decimal positive and the sign is in the structure. there is an
alternate way where the number is stored in excess-3 signed mode with no
external sign flag. i chose this format as only subtraction with a
negative result will require compensation. multiplcation requires no
extra work and conversions are more direct. division also is more
derect. with excess 3 signed values, you have more work on conversions
of negative numbers and with multiplication and division. subtraction is
simpler though. i will go over excess-3 and correct-6 algorithms
later. the current add and subtract code work is well commented with
regard to this algorithm so read it.

is that clear so far? :)

wait until you get into the algorithms. :)

code wise we have the structure and a decent set of macros that define
various sizes and masks. only a few need to be configured (see bignum.h
at the top for those) and the rest are derived.

also there are several operational macros to define, init and manipulate
nibble pointers. these are tested and should be stable. they are (and
will be) used by code to mung nibbles in mch of the code. a nibble
pointer is 3 variable with a common (an argument to all the nibble
macros) base name. they are the word pointer, a nibble offset in the
word and a nibble mask. the logic used is fairly clear from the code and
should be portable to any word size.

we have a basic version of bcd addition and subtraction working. they
are multiword and can be extended. scaling support in both aligning
numbers and dealing with exponents and such need to be done.

there is a integer to bignum routine and some constructor code. the
malloc/free stuff needs to be #ifdef'ed to support either libc
amlloc/free or parrot alloc and leak (picked up by gc). we want support
for malloc/free as we will test this as a standalong library and not
rely on parrot for anything. also there is a simple dump routine for
debugging.

i have designs in mind for multiplication (with caching of partial
products) and division (also with caching). more on that later.

the current tarball is at: stemsystems.com/bignum.tar.gz

it should compile directly on most (all?) 32 systems as it doesn't do
much. the big_test prog can be played with and more examples can be
called. play with it as much as you want.

when we have something more real and substantial, we will want to cvs it
in the parrot tree. can someone deal with that? until then i will edit
the master file and take patches and update the tarball. i will email
when the tarball changes.

any questions? ideas? better code? 

i need some kicks to get back into more coding. i have much other real
world work so don't feel shy about taking on stuff. i will help with
algorithms and anything i can including code. scaling support can get
tricky and i will write about that. also my mult/divide ideas will get
written up soon (i hope).

thanx,

uri

-- 
Uri Guttman  ------  uri@stemsystems.com  -------- http://www.stemsystems.com
-- Stem is an Open Source Network Development Toolkit and Application Suite -
----- Stem and Perl Development, Systems Architecture, Design and Coding ----
Search or Offer Perl Jobs  ----------------------------  http://jobs.perl.org

• test by Jason Gloudon
• Re: test by Uri Guttman
• Re: test by Daniel Grunblatt
• Re: test by John M. Gamble
• Re: test by Uri Guttman
• Re: test by Jason Gloudon
• struct Bignum by Uri Guttman