everything began when i tried to find an algorithm for prime factor(iz)ing integers of any size within a reasonable time (let's say 0.1 seconds). i had to learn that this issue is still unsolved and will be unsolved forever. at last, the problem depends on the recognition of the prime factor itself.
my first attempt was a prime list based approach. if you create a list of all primes within the AutoIt limitation, you could easily create a factorizing algorithm out of it. so i implemented a fascinating fast ancient algorithm, the "Sieve of Eratosthenes", ca. 300 BC. since you only have to calculate primes up to the square root of the limitation, the numbers below 32,000,000 should be sufficient.
The Fundamental Theorem of Arithmetic: "Every natural number is either prime or can be uniquely factored as a product of primes in a unique way."
the list, saved to a textfile, resulted in incredible 16 mb and it took some 15 minutes to be created. okay, once you have the list, the rest is easy. but still not good enough, because only reading in the list takes about three seconds.
so i kept searching for better results and made my way deep into math science. i came across the Euclidean Algorithm, the Fermat theorem, the Goldbach conjecture, the Riemann hypothesis, Gauss and Carmichael numbers, the Zeta and Beta function and modern encryption algorithms, all of them deal with the same problem: how to determine that a number is a prime ?
the algorithms i finally implemented in my UDF are very strange: they are nearly impossible to explain and to calculate by hand, but transposed to computer language they result incredibly simple, just one or two loops and hardly 10 lines of codes. nevertheless the implementation is complicated. the numbers are looped some thousand times through, you have to deal with huge exponents that break every limit. in doing so you have to use a very interesting modern part of arithmetics called modular arithmetics.
please observe that you will, of course, not find any kind of primes list within the UDF, this would have been unfair.
on my way i came across a whole bunch of algorithms representing 2500 years of algebra, that i put together in one file. many of them i would judge very useful for other implementations.
i am not sure if they are all optimized, so be free to make suggestions if you find an improvement. on making prime functions, all that matters in the end is the calculation speed.
the zip file (Primes.zip) contains:
- _Primes.au3 : the UDFs
- _PrimesExamples.au3 : Examples for the UDFs
- PrimeSpiral.au3 : an implementation that visualizes primes in a very clever way based on Ulam's Prime Spiral
Main Functions :
_GetFactors ( $s_number )
_IsPrime ( $s_number )
_PrimeNext ( $s_number )
_PrimePrevious ( $s_number )
_RandomPrime ( $s_max [, $s_min] )
_IsTwinPrime ( $s_number )
_PrimeGap ( $s_number [, $s_mode] )
_PrimesInRange ( $s_max [, $s_min] )
_Triangular ( $s_count )
_IsTriangular ( $s_number )
_TriangularsInRange($s_max [, $s_min] )
Prime Related Math Functions :
_GCD ( $s_number1, $s_number2 = "-", $s_number3 = "-", $s_number4 = "-", $s_number5 = "-" )
(Greatest Common Divisor)
_ggT ( $s_number1, $s_number2 = "", $s_number3 = "", $s_number4 = "", $s_number5 = "" )
_LCM ( $s_number1, $s_number2 = "-", $s_number3 = "-", $s_number4 = "-", $s_number5 = "-" )
(Least Common Multiple)
_kgV ( $s_number1, $s_number2 = "", $s_number3 = "", $s_number4 = "", $s_number5 = "" )
_IsEven ( $s_number )
_IsOdd ( $s_number )
_Cross ( $s_number, $s_mode=0 )
_Factorial ( $s_number )
_LogX ( $s_Result, $s_Base )
_LogE ( $s_Result )
_Log10 ( $s_Result )
_Log2 ( $s_Result )
_RootX ( $s_Number, $s_Base )
_Swap ( ByRef $s_value1, ByRef $s_value2 )
Bit Operations :
_BitAND ( $s_value1 [, $s_value2 = 0] )
_BitLen ( $s_value )
_BitMid ( $s_value, $s_start, $s_count = 1000000000000000 )
_BitNOT ( $s_value )
_BitOR ( $s_value1 [, $s_value2 = 0] )
_BitShift ( $s_value, $s_shift )
_BitXOR ( $s_value1 [, $s_value2 = 0] )
_ModEx ( $s_base, $s_exp, $s_modulus )
_MulMod ( $x, $y, $N )
_Binary ( $s_number )
_FactorizeL ( $s_number, $s_mode = 0, $s_separator = "", $s_limit = 32000000 )
_CreatePrimeList ( [$s_limit = 32000000] )
_LoadPrimeList ( [$mode = 0, $file = "Primes-32000000.txt"] )
_GetFactorsL ( $s_number [,$a_Prime = 0] )
_CreatePrimeListEx ( ) NOT working
_CreatePrimeListMax ( ) NOT working
Numeric Conversions :
_IntToBin ( $s_number )
_BinToInt ( $s_string )
_IntToHex ( $hx_dec [, $hx_length] )
_HexToInt ( $hx_hex )
_IntToAny ( $s_number, $s_base [, $s_length] )
_AnyToInt ( $s_string, $s_base )
_AnyToAny ( $s_string, $s_base1, $s_base2 [, $s_length] )
_Arabian ( $input )
_Roman ( $input )
_1000 ( $x, $s_separator = "" )
_Eratosthenes ( $s_max )
_Euclid ( $a, $b )
_DivideDown ( $s_number )
_SPRP ( $s_number )
_Miller_Rabin ( $s_number )
_Fermat ( $s_number )
_Pollard_p ( $s_number )
_Pollard_Rho ( $s_number )
_Pollard_Strassen ( $s_number )
_GetFactorsOld ( $s_number )
_IsPrimeOld ( $s_number )
Maybe anyone can tell me why "PrimeSpiral" is always started twice ? i can't find out why.
In 1963, Stanislav Ulam discovered a fascinating way to visualize primes. beginning with number 1 in the center, write down all consequent numbers in a spiral.
17---*---*---*--13 ... | | | * 5---*---3 * 29 | | | | | 19 * *---2 11 * | | | | * 7---*---*---* * | | *---*--23---*---*---*
mark all primes in a different color and the result is a suprising fractal-like structure. you will see big numbers of primes lined up in diagonal lines, and others vertically or horizontally. it is surprising because it seems to implement some kind of rule in prime distribution. But still, there has not been found one.
you can choose other base numbers, but the result will always be alike.
my program can also mark square and triangular numbers in this matrix. to see them clearly, choose a blue color like the background for the primes. you can also mark twin primes or differentiate the primes by color. or you can set a fixed diagonal and let the bases cycle. there's a zoom function and some other tools.
the algorithm to calculate the primes is the Sieve of Eratosthenes, so this is also a demonstration of how this works. the first ten numbers are quite slow (because the lower the number, the more often it has to strike out its multiples), but then the spiral explodes and will fill your screen within 50 seconds. the program is faster if you click on the child guis, because the graphic will not be refreshed then. when the flickering begins, it means that the refreshing needs more time than calculating a new square of numbers. so this is impressingly fast !
everytime you start the program you should leave it build at least once a complete full screen run, so that the prime matrix can be filled. otherwise you will find false primes on the next runs.
as an example exploration, set offset (=base) to primes 17 or 41. you can find a long continous prime diagonal (NE-SW) through the center, that ends on both sides right at the starting points of the two square number diagonals (NW-SE), so that these 3 diagonals build a perfect, right angled, continuous Z. (still this is not the famous Zeta function, but it's close !) There should be more offset primes that build the same pattern, with an increasing central prime diagonal size.
okay, have fun and interesting conclusions with my programs.
Edit: 23.10. : updated _Primes.au3 : v1.2 (corrected _Factorial, improved _IsPrime, _PrimeNext and PrimePrevious, corrected loop declarations) prev downloads : 23
Edited by jennico, 23 October 2008 - 01:41 AM.