[R] integer factorization

[Martin Maechler]

>>>>> "ChrBu" == Christoph Buser <buser at stat.math.ethz.ch>
>>>>>     on Wed, 5 Jan 2005 11:13:30 +0100 writes:

    ChrBu> Hi Robin
    ChrBu> There is a function factorize() in the package conf.design

    ChrBu> library(conf.design)
    ChrBu> factorize(60)
    ChrBu> [1] 2 2 3 5

yes, as quick search on Jonathan Baron's site
(with the nice new  URL  http://search.R-project.org/ !!)
also shows.

    ChrBu> Hope this helps

yes, merci, Christoph!

Note that conf.design is by Bill Venables himself who has also
been involved in the discussion on S-news, ca. 1996, and 1998
about fast / useful prime number and factorization S functions.

>From that time I still have nice file of function definitions,
of other people's and my own functions.
Last summer I've also found a few tricks to speed up {for R} Bill's
already quite fast  primes() function.

Also, I have had a factorize() function that is considerable
faster than the one in 'conf.design' at least for the examples
I've tried.

For the moment, my code and examples are available from
  ftp://stat.ethz.ch/U/maechler/R/  prime-numbers-fn.R
and                                 prime-numbers.R

E.g.,
 > source("ftp://stat.ethz.ch/U/maechler/R/prime-numbers-fn.R")
 > factorize(20:25)
 $"20"
      p m
 [1,] 2 2
 [2,] 5 1

 $"21"
      p m
 [1,] 3 1
 [2,] 7 1

 $"22"
       p m
 [1,]  2 1
 [2,] 11 1

 $"23"
       p m
 [1,] 23 1

 $"24"
      p m
 [1,] 2 3
 [2,] 3 1

 $"25"
      p m
 [1,] 5 2

which is even a bit closer to what Robin was looking for.

{Note that my factorize() is uses prime.sieve() whereas I show
 in other examples that Bill Venables' primes() is much faster
 and my modification of it is even faster;
 also for the case of factorizing( <long vector> ), it would be
 better to make use of *stored* prime numbers...
}
----

and  "ftp://stat.ethz.ch/U/maechler/R/prime-numbers.R"
contains more examples using (and comparing) the function
definitions in ..../prime-numbers-fn.R

Of course, to do this properly one should really use special
code (in C) and maybe even consider long integers etc.  
It's however quite astonishing how fast the primes() and
factorize() functions run, and I have been wondering more than
once if they shouldn't be added to ``standard R'', i.e., the
"utils" package.

Martin