123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146 |
- // factor a polynomial or integer
- #include "stdafx.h"
- #include "defs.h"
- void
- eval_factor(void)
- {
- push(cadr(p1));
- eval();
- push(caddr(p1));
- eval();
- p2 = pop();
- if (p2 == symbol(NIL))
- guess();
- else
- push(p2);
- factor();
- // more factoring?
- p1 = cdddr(p1);
- while (iscons(p1)) {
- push(car(p1));
- eval();
- factor_again();
- p1 = cdr(p1);
- }
- }
- void
- factor_again(void)
- {
- int h, n;
- save();
- p2 = pop();
- p1 = pop();
- h = tos;
- if (car(p1) == symbol(MULTIPLY)) {
- p1 = cdr(p1);
- while (iscons(p1)) {
- push(car(p1));
- push(p2);
- factor_term();
- p1 = cdr(p1);
- }
- } else {
- push(p1);
- push(p2);
- factor_term();
- }
- n = tos - h;
- if (n > 1)
- multiply_all_noexpand(n);
- restore();
- }
- void
- factor_term(void)
- {
- save();
- factorpoly();
- p1 = pop();
- if (car(p1) == symbol(MULTIPLY)) {
- p1 = cdr(p1);
- while (iscons(p1)) {
- push(car(p1));
- p1 = cdr(p1);
- }
- } else
- push(p1);
- restore();
- }
- void
- factor(void)
- {
- save();
- p2 = pop();
- p1 = pop();
- if (isinteger(p1)) {
- push(p1);
- factor_number(); // see pollard.cpp
- } else {
- push(p1);
- push(p2);
- factorpoly();
- }
- restore();
- }
- // for factoring small integers (2^32 or less)
- void
- factor_small_number(void)
- {
- int d, expo, i, n;
- save();
- n = pop_integer();
- if (n == (int) 0x80000000)
- stop("number too big to factor");
- if (n < 0)
- n = -n;
- for (i = 0; i < MAXPRIMETAB; i++) {
- d = primetab[i];
- if (d > n / d)
- break;
- expo = 0;
- while (n % d == 0) {
- n /= d;
- expo++;
- }
- if (expo) {
- push_integer(d);
- push_integer(expo);
- }
- }
- if (n > 1) {
- push_integer(n);
- push_integer(1);
- }
- restore();
- }
|