Nom

Number — An overview of the Number toolbox.

Purpose

The goal of this toolbox is to provide several Number theory related algorithms. The following is a list of the current features:

  • primality test

  • greatest common divisor

  • least common multiple

  • list of primes lower than

  • factoring into primes

Most algorithms are "naive" implementations. Many features are missing so that the current state is more a "toy" toolbox.

Numbers managed by the algorithms

Since Scilab basic data type is the double precision floating point number, we use this data type as our basic integer representation. Indeed, this representation allows to manage signed integers from -2^53 up to 2^53.

The current implementation could be extended to arbitrary precision integers. To my knowledge, there is no such tool for Scilab. If that library was available and support the operations required by the algorithms, simply modifying the number_check function should allow to manage such integers.

Quick start

In the following example, we compute the greatest common divisor of 84 and 18 and find 6. Then we factor 84 into primes and check that the product of the factors is indeed 84. Then we factor 18 into primes and confirm that the GCD of 84 and 18 is indeed 6. Then we compute the LCM of 84 and 18 and find 252. Finally, we check that the product of the GCD and the LCM is, as expected, the product of the two numbers.

 
number_gcd ( 84 , 18 )
number_factor ( 84 )
prod ( [2.    2.    3.    7. ] )
number_factor ( 18 )
number_lcm ( 84 , 18 )
6 * 252, 84*18
 

This produces the following output.

 
-->number_gcd ( 84 , 18 )
 ans  =
    6.  
-->number_factor ( 84 )
 ans  =
    2.    2.    3.    7.  
-->prod ( [2.    2.    3.    7. ] )
 ans  =
    84.  
-->number_factor ( 18 )
 ans  =
    2.    3.    3.  
-->number_lcm ( 84 , 18 )
 ans  =
    252.  
-->6 * 252, 84*18
 ans  =
    1512.  
 ans  =
    1512.  
 

In the following example, we decompose various numbers into various bases. Finally, we use the number_barygui function to draw a gui which displays digits.

 
d = number_tobary ( 4 )'
d = number_tobary ( 4 , 3 )'
d = number_tobary ( 5 , 3 )'
d = number_tobary ( 4 , 2 , "bigendian" )'
d = number_tobary ( 4 , 2 , "bigendian" , 8 )'
number_barygui(4);
 

This produces the following output.

 
-->d = number_tobary ( 4 )'
 d  =
    1.    0.    0.  
-->d = number_tobary ( 4 , 3 )'
 d  =
    1.    1.  
-->d = number_tobary ( 5 , 3 )'
 d  =
    1.    2.  
-->d = number_tobary ( 4 , 2 , "bigendian" )'
 d  =
    0.    0.    1.  
-->d = number_tobary ( 4 , 2 , "bigendian" , 8 )'
 d  =
    0.    0.    1.    0.    0.    0.    0.    0.  
-->number_barygui(4);
 

Authors

DIGITEO - Michael Baudin - 2009-2010

Farid Belahcene

John Burkardt, 2004

TODO

  • implement a fast factoring algorithm

Acknowledgements

Pierre Maréchal

Bibliography

“The Art of Computer Programming”, Donald Knuth, Volume 2, Seminumerical Algorithms.

“Introduction to algorithms”, Cormen, Leiserson, Rivest, Stein, 2001, McGraw-Hill.