1 | # factor a polynomial or integer
|
2 |
|
3 |
|
4 |
|
5 | Eval_factor = ->
|
6 | push(cadr(p1))
|
7 | Eval()
|
8 |
|
9 | push(caddr(p1))
|
10 | Eval()
|
11 |
|
12 | p2 = pop()
|
13 | if (p2 == symbol(NIL))
|
14 | guess()
|
15 | else
|
16 | push(p2)
|
17 |
|
18 | factor()
|
19 |
|
20 | # more factoring?
|
21 |
|
22 | p1 = cdddr(p1)
|
23 | while (iscons(p1))
|
24 | push(car(p1))
|
25 | Eval()
|
26 | factor_again()
|
27 | p1 = cdr(p1)
|
28 |
|
29 | factor_again = ->
|
30 |
|
31 | save()
|
32 |
|
33 | p2 = pop()
|
34 | p1 = pop()
|
35 |
|
36 | h = tos
|
37 |
|
38 | if (car(p1) == symbol(MULTIPLY))
|
39 | p1 = cdr(p1)
|
40 | while (iscons(p1))
|
41 | push(car(p1))
|
42 | push(p2)
|
43 | factor_term()
|
44 | p1 = cdr(p1)
|
45 | else
|
46 | push(p1)
|
47 | push(p2)
|
48 | factor_term()
|
49 |
|
50 | n = tos - h
|
51 |
|
52 | if (n > 1)
|
53 | multiply_all_noexpand(n)
|
54 |
|
55 | restore()
|
56 |
|
57 | factor_term = ->
|
58 | save()
|
59 | factorpoly()
|
60 | p1 = pop()
|
61 | if (car(p1) == symbol(MULTIPLY))
|
62 | p1 = cdr(p1)
|
63 | while (iscons(p1))
|
64 | push(car(p1))
|
65 | p1 = cdr(p1)
|
66 | else
|
67 | push(p1)
|
68 | restore()
|
69 |
|
70 | factor = ->
|
71 | save()
|
72 | p2 = pop()
|
73 | p1 = pop()
|
74 | if (isinteger(p1))
|
75 | push(p1)
|
76 | factor_number(); # see pollard.cpp
|
77 | else
|
78 | push(p1)
|
79 | push(p2)
|
80 | factorpoly()
|
81 | restore()
|
82 |
|
83 | # for factoring small integers (2^32 or less)
|
84 |
|
85 | factor_small_number = ->
|
86 |
|
87 | i = 0
|
88 | save()
|
89 |
|
90 | n = pop_integer()
|
91 |
|
92 | if (isNaN(n))
|
93 | stop("number too big to factor")
|
94 |
|
95 | if (n < 0)
|
96 | n = -n
|
97 |
|
98 | for i in [0...MAXPRIMETAB]
|
99 |
|
100 | d = primetab[i]
|
101 |
|
102 | if (d > n / d)
|
103 | break
|
104 |
|
105 | expo = 0
|
106 |
|
107 | while (n % d == 0)
|
108 | n /= d
|
109 | expo++
|
110 |
|
111 | if (expo)
|
112 | push_integer(d)
|
113 | push_integer(expo)
|
114 |
|
115 | if (n > 1)
|
116 | push_integer(n)
|
117 | push_integer(1)
|
118 |
|
119 | restore()
|
120 |
|
121 |
|