Re: TI-M: Re: TI-Math Digest V1 #22

To: <ti-math@lists.ticalc.org>
Subject: Re: TI-M: Re: TI-Math Digest V1 #22
From: "Scott Noveck" <noveck@pluto.njcc.com>
Date: Thu, 8 Jun 2000 21:35:26 -0400
References: <20000608220014.4235EA4030@towerguard.edu.sollentuna.se>
Reply-To: ti-math@lists.ticalc.org


> Actually, there should be no noticeable delay when dividing a 32-bit
number

32-_digit_ number.  Do you still imagine that division of a 32-digit BCD
number by all those primes could be done so quickly?  I suppose it may not
be that difficult. . .

> Raw binary (as opposed to BCD) seems to work decently on the Z80 in my
> implementation (and that's not even done too well...), so why wouldn't it
> work on an M68K?  In my opinion, raw binary would be the way to go,
> especially with integers and especially on the M68K...

Because trying to work with 613-digit decimal numbers (floats) in raw binary
would be horrendous.  If you're going to limit your numbers to only a few
bytes, raw binary may be fine (although 64 bits may be a bit much for raw
binary floats?), but trying to take a binary number and converting it to a
decimal number could take very, very, very, very long when the resulting
decimal number is as long as 613 digits =)

> Similarly, for every prime p, p = 1 (mod
> 2*3*5), p = 7 (mod 30), p = 11 (mod 30), p = 13 (mod 30), p = 17 (mod 30),
p
> = 19 (mod 30), p = 23 (mod 30), or p = 29 (mod 30).

So, for every prime this _is_ true, but is it not true for every number
that's not prime (the contrapositive)?  I imagine so, but I'm just checking
=)

> I suppose I should
> put in that when creating a "congruency list" for prime numbers (such as
the
> 1, 7, 11, 13, ..., 29 list above), don't create the list based on
primality,
> but rather whether the number is divisible by 2, 3, and/or 5 (with modulus
> 30)

If we're using BCD numbers, then this sounds great - after mod 30, it's
_very_ easy to test divisibility by 2, 3, or 5 in BCD since each digit is
kept in base 10 form.  Were we to use hex numbers, division by 3 or 5 would
be a pain - but with BCD, we can extract the last digit by itself and test
whether it's even (check bit 0) or 5; otherwise, testing for divisibility by
3 is as easy as adding the digits and checking if the resulting number is 3,
6, or 9.  I would think that in this instance, BCD math could be faster than
64-bit or larger binary numbers.

> 2, 3, 5, and/or 7 (with modulus 210); or 2, 3, 5, 7, and/or 11 (with
> modulus 2310).

I doubt that this would be very efficient, since in most cases we'll be
wasting time attempting division by 7 (and possibly 11) when it would be
much faster to mod with 30 and save the time spent in that division.

> I think that's about all you'd need to know; probably went overboard there
on
> the explanation... ;)

Not at all, I appreciate it =)

    -Scott

References:

From: