factor.cpp

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