mfactor.cpp

   1 // For odd n, returns the largest factor less than or equal to sqrt(n)
   2
   3 #include "stdafx.h"
   4 #include "defs.h"
   5
   6 #if 0 // not used anymore
   7
   8 unsigned int *
   9 mfactor(unsigned int *n)
  10 {
  11         unsigned int *r, *root, *t, *two, *x, *y;
  12
  13         two = mint(2);
  14
  15         root = msqrt(n);
  16
  17         // y = 1;
  18
  19         y = mint(1);
  20
  21         // x = 2 isqrt(n) + 1
  22
  23         t = madd(root, root);
  24         x = madd(t, y);
  25         mfree(t);
  26
  27         // r = isqrt(n) ^ 2 - n
  28
  29         t = mmul(root, root);
  30         r = msub(t, n);
  31         mfree(t);
  32
  33         mfree(root);
  34
  35         while (1) {
  36
  37                 if (MZERO(r)) {
  38
  39                         // n = (x - y) / 2
  40
  41                         t = msub(x, y);
  42                         n = mdiv(t, two);
  43                         mfree(t);
  44
  45                         mfree(r);
  46                         mfree(x);
  47                         mfree(y);
  48                         mfree(two);
  49
  50                         return n;
  51                 }
  52
  53                 // r = r + x
  54
  55                 t = madd(r, x);
  56                 mfree(r);
  57                 r = t;
  58
  59                 // x = x + 2
  60
  61                 t = madd(x, two);
  62                 mfree(x);
  63                 x = t;
  64
  65                 while (1) {
  66
  67                         // r = r - y
  68
  69                         t = msub(r, y);
  70                         mfree(r);
  71                         r = t;
  72
  73                         // y = y + 2
  74
  75                         t = madd(y, two);
  76                         mfree(y);
  77                         y = t;
  78
  79                         if (MSIGN(r) == -1 || MZERO(r))
  80                                 break;
  81                 }
  82         }
  83 }
  84
  85 void
  86 test_mfactor(void)
  87 {
  88         unsigned int *n;
  89         n = mint(377);
  90         n = mfactor(n);
  91         printf("%d", n[0]);
  92 }
  93
  94 #endif