



Guides & Solutions (Not For Questions) Post your guides here (No links to Blogs accepted). You can also append your comments/questions to a guide, but don't start a new thread to ask a question. Use another forum for that. 
18th November 2012, 11:30 PM

"Shells" (of a sub world)


Join Date: May 2011
Location: Confoederatio Helvetica (Swissh)
Age: 37
Posts: 4,277


[BASH]: Prime Numbers
Heyas
Its been a while since i've done some math,
so out of curiousity and 'fun' i wanted to write a bash script doing that.
AFAIK: A prime number is defined by any number that is only dividable by 1 or itself.
AFAIK: Bash works only with integer numbers, which uses no coma seperation.
Prime Numbers are not EVEN
But 2 beeing the only expection!
So at first a think of a function that helps to me skip every even number (eg 4,8,18,100), to save some 'math power'.
So that function simply divides provided number by 2 and looks if the half number * 2 equals the original number.
I've modified the function so i can pass a 2nd argument which is used when i want to divide the number with something diffrent than 2.
Still thinking that (17/3)*3 is not 17 when counting with int values.
Getting the prime number
So to get the prime numbers i pass every uneven number to check if it by the prime function.
The prime function expects a prime number to be not even as long its dividing number is not 1 or itself.
So it divide the prime counter with every number until current one, and as long it is not even, it expects to be NON prime.
Ok... until i wrote this, i got my script fixed mainwhile., so copy paste from programming to guides & Solutions.
So lets share it for those with homeworks
PHP Code:
#!/bin/bash
#
# Description: Simply calculates prime numbers between min and max variable
# Lisence: GPL v3
# Date created: 2012.11.18
# Date changed: 2012.11.18
# Written by: Simon A. Erat, erat . simon æ gmail . com
script_version=0.1
#
# Variables
#
prime_min=3
prime_max=4000
C=$prime_min
#
# Title
#
clear
echo "Calculating prime numbers ($script_version)"
#
# Subs
#
isEven() { # NUM1 [ NUM2]
# Check if number is even, if NUM2 is missing its divideing by 2.
# Returns 0 for success, 1 otherwise.
retval=1
num=$1
[ "" = "$2" ] && div=2  div=$2
check=$[ $num / $div ]
[ $num eq $[ $check * $div ] ] && retval=0
return $retval
}
isPrime() { # NUM
# Verifies all numbers from 2 to NUM1
# If none returns even, it returns 0, 1 otherwise
retval=0
count=2
while [ $count le $[ $1  1 ] ];do
# We already skiped even numbers, so no need to use them now.
if ! isEven $count
then # Like: 15 / 3 = 5 = even
isEven $1 $count && retval=1 && break
fi
((count++))
done
return $retval
}
#
# Display
#
printf "\n\rPrime numbers from $prime_min to $prime_max\n:: Calculating... "
while [ $C le $prime_max ];do
# Dont need to check even numbers
if ! isEven $C
then # Is it a prime number?
if isPrime $C
then printf " $C"
#else printf "."
fi
fi
((C++))
done
echo
echo
echo "Hope this helped :)"
echo
Hope this helps or you have fun with it
__________________
EFI Cheatsheet :: http://forums.fedoraforum.org/showthread.php?t=298546
Video Handler Script (VHS) (mass reencode videos, screenrecorder, console music/webradio player, ...) :: http://forums.fedoraforum.org/showthread.php?t=299182
Windows 8+ & Fedora 20+ Dualboot :: http://forums.fedoraforum.org/showthread.php?t=298161
Last edited by sea; 19th November 2012 at 07:45 PM.

18th November 2012, 11:49 PM

Registered User


Join Date: Mar 2009
Location: Lancaster, UK
Posts: 928


Re: [BASH]: Prime Numbers
Could you use the mod operator (%) to check if a number is even? (n%2; returns 0 if n is even. I think thats the correct syntax. Also some code missing from the end?

19th November 2012, 12:29 AM

"Shells" (of a sub world)


Join Date: May 2011
Location: Confoederatio Helvetica (Swissh)
Age: 37
Posts: 4,277


Re: [BASH]: Prime Numbers
Thank you, i'll have a look into %.
As long you see:
Code:
echo
echo "Hope this helped :)"
echo
at the end, its all good. (you can scroll the displaying textarea)
__________________
EFI Cheatsheet :: http://forums.fedoraforum.org/showthread.php?t=298546
Video Handler Script (VHS) (mass reencode videos, screenrecorder, console music/webradio player, ...) :: http://forums.fedoraforum.org/showthread.php?t=299182
Windows 8+ & Fedora 20+ Dualboot :: http://forums.fedoraforum.org/showthread.php?t=298161

19th November 2012, 12:51 AM

Guest


Posts: n/a


Re: [BASH]: Prime Numbers
Ehh
2 is a prime and its even !
Aside from 2, all primes are odd (2n+1)
Aside from 2 & 3, all primes are of the form (6n1) or (6n+1)
Aside from 2,3,5,7,11,13 all primes are of the form (30n +{1,7,11,13})
That sort of thinking doesn't reduce the computation very much.
Consider that all nonprimes 'N' have a prime factor <= sqrt(N).
Examine the more advanced sieves (the sieve of atkin).

19th November 2012, 08:38 AM

Registered User


Join Date: Jun 2010
Location: Lost...
Posts: 1,300


Re: [BASH]: Prime Numbers
You can save some computationnal power by discarding the obvious multiples.
For instance, for num > 5:
Code:
case ${num:${#num}1:1} in
02468395)
disgard num;;
*)
continue;;
esac
__________________
:confused:

19th November 2012, 10:45 AM

Registered User


Join Date: Mar 2009
Location: Lancaster, UK
Posts: 928


Re: [BASH]: Prime Numbers
Quote:
Originally Posted by sea
Thank you, i'll have a look into %.
As long you see:
Code:
echo
echo "Hope this helped :)"
echo
at the end, its all good. (you can scroll the displaying textarea)

Sorry, I was looking at it on my phone and it did not sho that I could scroll in the code.

19th November 2012, 12:57 PM

Guest


Posts: n/a


Re: [BASH]: Prime Numbers
Here. This calculates primes <250000 in about the same times as the OPs does <4000.
It's still not good.
Code:
#!/bin/bash
# not very good primes program
# vars 
prime_max=250000
# initial values, do not change
cmax=1
cmaxsqr=1
# functions 
# is arg1 a multiple of arg2 ?
isMultiple() { return $((($1%$2) != 0)) ; }
# is the next consecutive prime
isNextPrime() {
while [ $1 gt $cmaxsqr ]
do
((cmax++))
cmaxsqr=$(($cmax * $cmax))
done
for((count=3; count<=cmax; count+=2))
do
# isMultiple $1 $count
# inline the function
[ $(($1%$count)) eq 0 ] && return 1
done
return 0
}
#  main 
clear
echo "Calculating prime numbers ($script_version)"
printf "\n\rPrime numbers to $prime_max\n:: Calculating... 2"
for((i=3; i<= $prime_max; i+=2))
do
isNextPrime $i && printf " $i"
done
printf "\ndone"

20th November 2012, 04:50 AM

Registered User


Join Date: Nov 2006
Location: Detroit
Posts: 6,611


Re: [BASH]: Prime Numbers
Here's a Perl version that calculates all the primes < 1,000,000 in about 5 seconds on my machine:
Code:
#!/usr/bin/perl
my $UPPER = 1000000;
my $sieve = "";
GUESS: for (my $guess = 2; $guess <= $UPPER; $guess++) {
next GUESS if vec($sieve,$guess,1);
print "$guess\n";
for (my $mults = $guess * $guess; $mults <= $UPPER; $mults += $guess) {
vec($sieve,$mults,1) = 1;
}
}
__________________
OS: Fedora 26 x86_64  Machine: HP Pavilion a6130n  CPU: AMD 64 X2 DualCore 5000+ 2.6GHz  RAM: 7GB PC5300 DDR2  Disk: 400GB SATA  Video: ATI Radeon HD 4350 512MB  Sound: Realtek ALC888S  Ethernet: Realtek RTL8201N

20th November 2012, 05:21 AM

"Shells" (of a sub world)


Join Date: May 2011
Location: Confoederatio Helvetica (Swissh)
Age: 37
Posts: 4,277


Re: [BASH]: Prime Numbers
WTF, it speeds up...
it took more time to calculate the first 4 numbers, than the rest of the 900'000.
And to make sure, a sieve is a synonym for filter?
__________________
EFI Cheatsheet :: http://forums.fedoraforum.org/showthread.php?t=298546
Video Handler Script (VHS) (mass reencode videos, screenrecorder, console music/webradio player, ...) :: http://forums.fedoraforum.org/showthread.php?t=299182
Windows 8+ & Fedora 20+ Dualboot :: http://forums.fedoraforum.org/showthread.php?t=298161

20th November 2012, 09:11 AM

Registered User


Join Date: Oct 2006
Location: Singapore, 新加坡
Posts: 989


Re: [BASH]: Prime Numbers
That is not surprising. It is easier to find low prime numbers then the high ones and when it does the algorithm needs to "mark" all its multiplies as nonprime. The first iteration for the first prime number (i.e. 2) practically has to mark the bit for all the even numbers within UPPER limit.
 Post added at 04:11 PM  Previous post was at 03:19 PM 
With that in mind, below revised version runs a tad faster than original one from Rupert.
Code:
#!/usr/bin/perl
my $UPPER = 1000000;
my $sieve = "";
print "2\n";
for (my $guess = 3; $guess <= $UPPER; $guess+=2) {
next if vec($sieve,$guess,1);
print "$guess\n";
for (my $mults = $guess * $guess; $mults <= $UPPER; $mults += $guess) {
vec($sieve,$mults,1) = 1;
}
}
Using my Intel i7, the original takes ~0.64 sec, while the revised one takes ~0.5 sec.
__________________
YaoWT  Leave no window unbroken ♪ (^｡^)

20th November 2012, 11:47 AM

Registered User


Join Date: Jul 2009
Location: England, UK
Posts: 969


Re: [BASH]: Prime Numbers
Quote:
Originally Posted by sea
And to make sure, a sieve is a synonym for filter?

This one is the Sieve of Eratosthenes.
In common english, sieve and filter are nearly the same of course. But "sieve" seems to be the word that has historical precedence in this context (and "filter" has a very specific meaning in the mathematics of ordered sets).

21st November 2012, 12:21 AM

Registered User


Join Date: Oct 2007
Location: Freedonia
Age: 67
Posts: 3,007


Re: [BASH]: Prime Numbers
You can speed things up, weitjong, by only starting your marking multiples of a new prime with its square, because all smaller ones will already be marked. And that means that once you've checked the square root of your limit you can stop because all the primes will be marked.
__________________
Registered Linux user #470359 and permanently recovered BOFH.
Any advice in this post is worth exactly what you paid for it.

21st November 2012, 06:10 AM

Registered User


Join Date: Oct 2006
Location: Singapore, 新加坡
Posts: 989


Re: [BASH]: Prime Numbers
Believe it or not, I had attempted to do just that the first thing after reading Rupert's post. I soon realized Rupert's original version is already in optimized form. It already starts the first mults with the square of the prime itself. Although the marking could stop at the square root of the UPPER limit, the outer forloop itself still has to iterate until reaching the UPPER limit to print out the results themselves. Furthermore, the marking loop (the inner forloop) stops automatically after the $guess reaches the square root of the UPPER limit.
Unless, we split the marking and printing into two separate loops. The marking loop stops at square root while the printing one goes all the way.
__________________
YaoWT  Leave no window unbroken ♪ (^｡^)

21st November 2012, 07:24 AM

Guest


Posts: n/a


Re: [BASH]: Prime Numbers
Hmm  If you want fast, but not bash there are lot's better solutions than perl.
That was never the topic.
This one uses parigp package ...
Quote:
[stevea@hypoxylon EP]$ export MAX=1000000; time ( echo "primes(primepi($MAX))" gp p $MAX > /dev/null)
real 0m0.028s
user 0m0.021s
sys 0m0.006s

On same hardware ....
Quote:
[stevea@hypoxylon tmp]$ time ./perljunk >/dev/null
real 0m1.054s
user 0m1.023s
sys 0m0.003s

Not bad for an interpreted language, but ... the question of algorithm is key.
As we go to larger upper bounds ....
Pari with a 10 million upper bound ...
Quote:
[stevea@hypoxylon tmp]$ export MAX=10000000; time ( echo "allocatemem(500000000) ; primes(primepi($MAX))" gp p $MAX >/dev/null )
real 0m0.163s
user 0m0.130s
sys 0m0.027s

Pari at 100 million
Quote:
[stevea@hypoxylon tmp]$ export MAX=100000000; time ( echo "allocatemem(500000000) ; primes(primepi($MAX))" gp p $MAX > /dev/null )
real 0m1.497s
user 0m1.150s
sys 0m0.286s

Pari computes all primes to one billion in ~32 seconds here.
Quote:
[stevea@hypoxylon tmp]$ export MAX=1000000000; time ( echo "allocatemem(5000000000) ; primes(primepi($MAX))" gp p $MAX > /dev/null )
real 0m32.373s
user 0m10.931s
sys 0m5.691s

vs the perl script modified to 10 mill.
Quote:
[stevea@hypoxylon tmp]$ time ./perljunk > /dev/null
real 0m11.305s
user 0m10.935s
sys 0m0.005s

perl to 100million
Quote:
[stevea@hypoxylon tmp]$ time ./perljunk > /dev/null
real 1m59.252s
user 1m55.911s
sys 0m0.125s

Last edited by stevea; 21st November 2012 at 07:54 AM.

21st November 2012, 10:18 AM

Registered User


Join Date: Jul 2009
Location: England, UK
Posts: 969


Re: [BASH]: Prime Numbers
Well, if we're going to switch to a library written in a compiled language by worldleaders in computational number theory, then no doubt we can get some better results in terms of speed
At the opposite extreme, in case you've not seen it, here's an insane way to check for primality... (Works for anything from 2 upwards; no error checking on the input!)
Code:
#!/bin/bash
str=''
for (( i = 0; i < "$1" ; i++ )); do
str="$str"1
done
if echo "$str"  grep q E '^(11+)\1+$'; then
echo "$1 is not prime"
else
echo "$1 is prime"
fi

Thread Tools 
Search this Thread 


Display Modes 
Linear Mode

Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



Current GMTtime: 03:38 (Tuesday, 22082017)







