← Back to branch summary

~ubuntu-branches/debian/sid/genius/sid

« back to all changes in this revision

Viewing changes to lib/number_theory/factoring.gel

  • Committer: Package Import Robot
  • Author(s): Felipe Sateler
  • Date: 2014-04-07 15:43:04 UTC
  • mfrom: (1.2.6)
  • Revision ID: package-import@ubuntu.com-20140407154304-21r03zdnfc571kz0
Tags: 1.0.17-1
http://bugs.debian.org/716731
* Take over package from pkg-gnome
* New upstream release. Closes: #716731
* Bump standards version.
* Update Vcs fields to Git.
* Move to single-debian-patch

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/number_theory/factoring.gel
67
67
)
68
68
 
69
69
# Returns all factors of n, i.e., all numbers between 1 and n that divide
70
 
# n.
71
 
# FIXME: this is a naive implementation. Better would be to compute
72
 
# the prime factorization for n and then combine it in all possible ways.
 
70
# n.  For small n does a naive implementation by trying all factors
 
71
# up to square root, for large numbers does Factorize first and then
 
72
# combines the factors in all possible ways.
73
73
SetHelp("Factors", "number_theory", "Return all factors of a number")
74
 
function Factors(n) =
75
 
 (
 
74
function Factors(n) = (
76
75
  if not IsInteger(n) then
77
76
        (error("Factors: argument not an integer");bailout);
78
77
  if n == 0 then return null;
79
78
 
80
 
  front_list=[0];
81
 
  back_list=[0];
 
79
  list = null;
82
80
 
83
81
  if n < 0 then (
84
82
    n = -n;
85
 
    front_list=[0,-1]
 
83
    list = [-1]
86
84
  );
87
85
 
88
 
  for loop = 1 to floor(sqrt(n-1)) do
89
 
   (
90
 
    if Divides(loop,n) then
91
 
     (
92
 
      front_list=[front_list,loop];
93
 
      back_list=[n/loop,back_list]
94
 
     )
95
 
   );
96
 
 
97
 
  if IsPerfectSquare(n) then
98
 
    r = [front_list,sqrt(n),back_list]
99
 
  else
100
 
    r = [front_list,back_list];
101
 
  r@(2:elements(r)-1)
102
 
 )
103
 
 
104
 
SetHelp("FermatFactorization", "number_theory", "Attempt fermat factorization of n into (t-s)*(t+s), returns t and s as a vector if possible, null otherwise")
 
86
  # for small n do naive implementation which is faster
 
87
  if n < 100000 then (
 
88
    back_list=null;
 
89
 
 
90
    for loop = 1 to floor(sqrt(n-1)) do (
 
91
      if Divides(loop,n) then (
 
92
        list=[list,loop];
 
93
        back_list=[n/loop,back_list]
 
94
      )
 
95
    );
 
96
 
 
97
    if IsPerfectSquare(n) then
 
98
      r = [list,sqrt(n),back_list]
 
99
    else
 
100
      r = [list,back_list];
 
101
    r
 
102
  ) else (
 
103
    fnc = fn = Factorize (n);
 
104
    for j=2 to columns(fnc) do fnc@(2,j) = 0;
 
105
  
 
106
    do (
 
107
      list = [list, (prod j=2 to columns(fnc) do fnc@(1,j)^fnc@(2,j))];
 
108
    
 
109
      gotnext = false;
 
110
      for j = 2 to columns(fnc) do (
 
111
        if fnc@(2,j) < fn@(2,j) then (
 
112
          increment fnc@(2,j);
 
113
          gotnext = true;
 
114
          break
 
115
        ) else ( #fnc@(2,j) == fn@(2,j)
 
116
          fnc@(2,j) := 0
 
117
        )
 
118
      )
 
119
    ) while (gotnext); 
 
120
    SortVector(list)
 
121
  ) 
 
122
)
 
123
 
 
124
SetHelp("FermatFactorization", "number_theory", "Attempt Fermat factorization of n into (t-s)*(t+s), returns t and s as a vector if possible, null otherwise")
105
125
function FermatFactorization(n,tries) = (
106
126
  if not IsPositiveInteger(n) or not IsPositiveInteger(tries) then
107
127
        (error("FermatFactorization: arguments not positive integers");bailout);