Showing posts with label relative. Show all posts
Showing posts with label relative. Show all posts

Sunday, June 15, 2008

Shell Scripting, Factorial Primes And Huge Number Computations On Linux And Unix

Hey There,

I know it's the weekend when I don't get any hate mail regarding posts like yesterday's on producing prime numbers with the bash shell ;)

One truth about prime numbers is that, except for 5, no number ending in 5 can be a prime. Logic dictates that it will, of course, be divisible by itself and by the number 5, thereby removing it from the prime pool. Another thing you may have noticed is the output from the script itself which showed that it found 35 to be a "prime number." It also missed quite a few after 19 (23, 29 and 31, to be specific).

There's a reason I let it go; and not just so I'd have something easy to write about on a "Lazy Sunday" ;) I actually tested this script both on an OpenBSD box and Cygwin for Windows (Unfortunately, I have no Unix computers at my disposal on the weekends, but Linux is just as capable an OS). Neither one could get past 19, when listing out primes; both related to the same two basic problems. The two situations that resulted, when trying to determine higher primes, both had to do with my system limitations, so you might have been able to get higher numbers than I did before the script went South on you :)

The first issue is the theorem we used to determine the primes. Since Wilson's Theorem depends on factorial computation in order to determine a number's prime status, each succeeding number requires an additional operation, which make the numbers required to test divisibility grow at an alarming rate.

For instance, the factorials of 2, 3 or 4 are trivial:

2 = 2 * 1 --> Factorial equals 2
3 = 3 * 2 * 1 --> Factorial equals 6
4 = 4 * 3 * 2 * 1 --> Factorial equals 24


and you can see how the numbers can begin to get large very quickly.

The second issue is the capacity of the Linux or Unix operating system to handle extremely large numbers. Although both of my systems are running 32 bit OS's, the 64 bit OS will have to eventually fail as well. On a 32 bit system, the magic number 20 is where the wrap-around occurs and the numbers become so large that the system can misinterpret them as negative something-or-other. Here are my two example outputs (truncated):

For Cygwin on 32 bit XP, you can see this in the script when you invoke bash with the -x flag, as it hits the breaking point at the number 22 (soooo close to 23 ;)

...
+ count=22
+ '[' 22 -le 22 ']'
++ prime_number 22
++ local prime=22
++ p_minus_1=21
+++ factorial 21
+++ local factorial_count=21
+++ '[' 21 -eq 0 ']'
+++ (( factor=20 ))
+++ (( 20 >= 1 ))
+++ factorial_count=420
+++ (( --factor ))
+++ (( 19 >= 1 ))
+++ factorial_count=7980
+++ (( --factor ))
...
+++ (( --factor ))
+++ (( 2 >= 1 ))
+++ factorial_count=-4249290049419214848
...


at this point, the test for divisibility becomes unreliable, at best.

On OpenBSD, 32 bit, the results were exactly the same:

...
+++ (( --factor ))
+++ (( 2 >= 1 ))
+++ factorial_count=-4249290049419214848
...


Naturally, then, every number tested for "prime status" by our prime number shell script, beginning with 22 couldn't be tested correctly, resulting in many more surprising results like 35 ;)

In any event, hopefully, the script helped make at least one method to determine primes more accessible or understandable. As we noted, also, in yesterday's post, no one has been able to define the largest prime number yet. Yesterday's script gives you a pretty clear idea of the reason. When faced with an infinite number of integers, the requirements for calculation, alone, make this an impossible task. But, basically, the reasons all boil down to the same thing (although, if you look around the web, there are a few unprovable - in the absolute sense - theories that claim the number can be known):

The nature of integers is infinite. If you think of the highest number you can and add 1, you're one step closer to being frustrated for the rest of your life ;)

Also, for clarity's sake, since the mathematics in my head don't always match what I type, I thought I'd save you some paraphrasing and just dump two definitions here on the page; for composite numbers and relative primes (with my side-notes and apologies):

Relative Primes: The integers a and b are relatively prime if they have no common factor other than 1 or, equivalently, if their greatest common divisor is 1 (Note that this was correctly defined yesterday, but not thoroughly enough, since I didn't mention the fact that, although the numbers can't be primes and must have the greatest common factor of 1, I neglected to mention that neither pair of numbers could have any other common factors. A fairly large distinction, but lost in the mix when I was typing. For instance, 6 and 35 are relative primes, while 6 and 36 aren't, since they both share a common factor of being divisible by 3. ...My mind can be a terrible thing ;)

Composite Numbers: These are any positive integers which have a positive divisor other than one or themselves (While these can be derived by multiplying any two prime numbers, which I pointed out, the less complicated definition is that composite numbers are any number that isn't a prime. The multiplication of any 2 primes to create a composite is more of a cool little frill than a necessity. It's a lot easier to wrap your head around when you look at it that way ;)

But, as promised, with regards to composites , we won't put a script out, so much as a description of a method, since the same mathematical boundaries would be hit performing this operation:

1. Run yesterday's script, or pick up a prime number table that will start with 2; the first real prime (check out yesterday's post on producing prime numbers for the reasons 1 and 0 aren't considered primes).

2. Remove every number in the prime table from the larger set of all numbers.

Voila: You have all of the composite numbers, although you will most probably never ever find them all ;)

Here's to another month or so of non-math-related posts ;)

Cheers,

, Mike

Saturday, June 14, 2008

Shell Script To Produce Prime Numbers On Linux And Unix

Hey There,

You might recall (quite a while back) the last time we put out a Linux or Unix script involving a somewhat-complex mathematical formula. The most recent post had to deal with factorial generation and the only other mostly-math post we did prior to that was about generating Fibonacci numbers up to any user-defined limit.

Today we're going to look at a similar issue, and develop a similar script. This time we'll work on something that, on its face, seems a bit easier to figure out. Today we're going to create a script that will list out all "prime" numbers up to a user-defined limit. We'll stay away from "relative primes" since (by definition) any two numbers, that aren't primes, share a greatest common factor (Sometimes referred to as the lowest common denominator in fractions) of 1. So non-prime numbers like 9 (1 x 3 x 9) and 25 (1 x 5 x 25) are considered relative primes. The definition basically applies to any numbers that aren't primes. You could easily derive those just by removing all the prime numbers from the positive integer set you define when you invoke the script, which can be easily done, like this:

host # ./primes.sh 100

Composite numbers are the result of the multiplication of prime numbers. We'll take a look at scripting out composites for our next post. It should be a natural extension of today's script.

It's interesting to note, though, that the number 1 is not considered a prime, because it only has one factor: itself. All other numbers, that are available for prime status, have two factors: themselves and themselves divided by 1 (with the result being a positive integer). Of course, the number 1 divided by 1 is zero; therefore, it only has one factor and it's not a prime. It is also not considered a composite. We'll be avoiding the dreaded zero today, as well, since it's neither a prime nor a composite either.

With all that muck out of the way (I hope ;), let's take a look at defining prime numbers on a formula-based scale. There is an excellent reference online at mathforum.org that goes into detail about many different ways (some better, some worse) to go about deriving primes to the nth degree. For our purposes, we're going to dispense with the Greek alphabet and look at solving the problem as purely as possible, even though that might not be the "most efficient" way to do it. Sometimes (especially if you're not a math wizard, like me), understanding how to generate numbers that meet certain criteria, is more important than applying advanced mathematical formulae which, for all I know, may or may not even be completely valid. If you're ever up for twisting your brain into a knot, try to absolutely prove any advanced mathematical formula. For kicks, ask an advanced mathemetician to do the same ;)

For those of you who are curious (since there are so many theorems out there), our script today is based on Wilson's Theorem, which basically states:

An integer p > 1 is prime if and only if the factorial (p - 1)! + 1 is divisible by p

In other words, if you take your chosen number, subtract 1 from that, get the factorial value (which we've gone through in more detail in our post regarding factorial generation) of the resulting subtraction and then add 1 to it, the number is only prime if the modulus (or remainder) of that resulting number's division by the original number is equal to 0 (or, depending on how you prefer to think of it, if the resulting number is absolutely divisible by the original number).

I hope you enjoy this script. I wangled the factorial function so that it's quite a bit faster than the "bash" method shown in our factorial generation post from earlier on. In fact, here's a look at the time savings from Linux running on a now-obsolete PC :)

host # time ./primes.sh.bak 35
Generating Prime Numbers Up To 35

2 3 5 7 11 13 17 19 35

All Set!


real 3m21.994s
user 0m18.445s
sys 0m40.857s

host # time ./primes.sh 35
Generating Prime Numbers Up To 35

2 3 5 7 11 13 17 19 35

All Set!


real 0m8.173s
user 0m1.464s
sys 0m2.407s


Note that this script can't find the highest prime number (I don't think anyone's figured that out yet), but it can figure out the highest prime number your system is capable of calculating. Close enough ;)

Cheers,


Creative Commons License


This work is licensed under a
Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

#!/bin/bash

#
# primes.sh - find all prime numbers up to a certain number
# 2008 - Mike Golvach - eggi@comcast.net
#
# Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
#

factorial () {
local factorial_count=$1
if [ "$factorial_count" -eq 0 ]
then
factorial_count=1
fi
for (( factor=$((factorial_count -1)); $factor >= 1; --factor ))
do
factorial_count=$(($factorial_count * $factor))
done
echo $factorial_count
}

prime_number () {
local prime=$1
p_minus_1=$(($prime - 1))
fact_p_minus_1=`factorial "$p_minus_1"`
fact_plus_1=$(($fact_p_minus_1 + 1))
echo $fact_plus_1
}

highest_number=$1

if [ -z $highest_number ]
then
echo
echo "Usage: $0 highestNumber"
echo
exit 1
fi

if [ $highest_number -eq 0 ]
then
echo
echo "Sorry. 0 is not a prime number"
echo
exit 0
elif [ $highest_number -eq 1 ]
then
echo
echo "Sorry. 0 and 1 are not prime numbers"
echo
exit 0
fi

echo "Generating Prime Numbers Up To $highest_number"
if [ $highest_number -eq 2 ]
then
echo
echo -n "2"
else
echo
echo -n "2 3 "
fi

count=4
while [ $count -le $highest_number ]
do
prime_return=`prime_number "$count"`
prime_test=$(($prime_return % count))
if [ $prime_test -eq 0 ]
then
echo -n "$count "
fi
count=$(($count + 1))
done

echo
echo
echo "All Set!"
echo

exit 0


, Mike