Changeset 4df33b in git

Timestamp:

Sep 28, 2010, 12:19:26 PM (13 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

c94e60f986f0fb36f24beb94af60519b01cb313c

Parents:

9a24da7e54cf925089f9c1420b3c4b79dc39eea6

Message:

tr. 275: primefactors(0), primefactors(<0)

git-svn-id: file:///usr/local/Singular/svn/trunk@13295 2c84dea3-7e68-4137-9b89-c4e89433aadc

File:

• Singular/misc_ip.cc (modified) (4 diffs)

Singular/misc_ip.cc

@@ -53 +53 @@
 }
 
-void divTimes_ui(mpz_t n, long d, int* times)
+void divTimes_ui(mpz_t n, unsigned long d, int* times)
 {
   *times = 0;
@@ -67 +67 @@
   mpz_clear(r);
   mpz_clear(q);
+}
+
+static inline void divTimes_ui_ui(unsigned long *n, unsigned long d, int* times)
+{
+  *times = 0;
+  unsigned long q=(*n) / d;
+  unsigned long r=(*n) % d;
+  while (r==0)
+  {
+    (*times)++;
+    (*n)=q;
+    q=(*n)/d; r=(*n)%d;
+  }
 }
 
@@ -180 +193 @@
   lists primes = (lists)omAllocBin(slists_bin); primes->Init(1000);
   int* multiplicities = new int[1000];
-
-  divTimes_ui(nn, 2, &tt);
-  if (tt > 0)
-  {
-    setListEntry_ui(primes, index, 2);
-    multiplicities[index++] = tt;
-  }
-
-  divTimes_ui(nn, 3, &tt);
-  if (tt > 0)
-  {
-    setListEntry_ui(primes, index, 3);
-    multiplicities[index++] = tt;
-  }
-
-  unsigned long p_ui=5; add = 2;
-  mpz_sqrt(sr, nn);
-  if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
-  int limit=mpz_get_ui(pb);
-  if ((limit==0)||(mpz_cmp_ui(pb,limit)!=0)) limit=1<<31;
-  while (p_ui <=limit)
-  {
-    divTimes_ui(nn, p_ui, &tt);
+  int positive=1;
+
+  if (!nlIsZero(n))
+  {
+    if (!nlGreaterZero(n)) 
+    {
+      positive=-1;
+      mpz_neg(nn,nn);
+    }
+    divTimes_ui(nn, 2, &tt);
     if (tt > 0)
     {
-      setListEntry_ui(primes, index, p_ui);
+      setListEntry_ui(primes, index, 2);
       multiplicities[index++] = tt;
-      //mpz_sqrt(sr, nn);
-      //if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
-      if (mpz_size1(nn)<=2) 
-      {
+    }
+
+    divTimes_ui(nn, 3, &tt);
+    if (tt > 0)
+    {
+      setListEntry_ui(primes, index, 3);
+      multiplicities[index++] = tt;
+    }
+
+    unsigned long p_ui=5; add = 2;
+    mpz_sqrt(sr, nn);
+    if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
+    int limit=mpz_get_ui(pb);
+    if ((limit==0)||(mpz_cmp_ui(pb,limit)!=0)) limit=1<<31;
+    while (p_ui <=limit)
+    {
+      divTimes_ui(nn, p_ui, &tt);
+      if (tt > 0)
+      {
+        setListEntry_ui(primes, index, p_ui);
+        multiplicities[index++] = tt;
+        //mpz_sqrt(sr, nn);
+        //if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
+        if (mpz_size1(nn)<=2) 
+        {
+          mpz_sqrt(sr, nn);
+          if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
+          unsigned long l=mpz_get_ui(sr);
+          if (l<limit) limit=l;
+          if (mpz_size1(nn)<=1)
+          {
+            unsigned long nn_ui=mpz_get_ui(nn);
+            while ((p_ui <=limit)&&(nn_ui>1))
+            {
+              divTimes_ui_ui(&nn_ui, p_ui, &tt);
+              if (tt > 0)
+              {
+                setListEntry_ui(primes, index, p_ui);
+                multiplicities[index++] = tt;
+                if (nn_ui>(limit/6)) limit=nn_ui/6;
+              }
+              p_ui +=add;
+              add += 2; if (add == 6) add = 2;
+            }
+            mpz_set_ui(nn,nn_ui);
+            break;
+          }
+        }
+      }
+      p_ui +=add;
+      add += 2; if (add == 6) add = 2;
+    }
+    mpz_set_ui(p, p_ui);
+    mpz_sqrt(sr, nn);
+    if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
+    while (mpz_cmp(pb, p) >= 0)
+    {
+      divTimes(nn, p, &tt);
+      if (tt > 0)
+      {
+        setListEntry(primes, index, p);
+        multiplicities[index++] = tt;
         mpz_sqrt(sr, nn);
         if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
-        unsigned long l=mpz_get_ui(sr);
-        if (l<limit) limit=l;
-      }
-    }
-    p_ui +=add;
-    add += 2; if (add == 6) add = 2;
-  }
-  mpz_set_ui(p, p_ui);
-  mpz_sqrt(sr, nn);
-  if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
-  while (mpz_cmp(pb, p) >= 0)
-  {
-    divTimes(nn, p, &tt);
-    if (tt > 0)
-    {
-      setListEntry(primes, index, p);
-      multiplicities[index++] = tt;
-      mpz_sqrt(sr, nn);
-      if ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(pb, sr) > 0)) mpz_set(pb, sr);
-    }
-    mpz_add_ui(p, p, add);
-    add += 2; if (add == 6) add = 2;
-  }
-  if ((mpz_cmp_ui(nn, 1) > 0) &&
-      ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(nn, b) <= 0)))
-  {
-    setListEntry(primes, index, nn);
-    multiplicities[index++] = 1;
-    mpz_set_ui(nn, 1);
+      }
+      mpz_add_ui(p, p, add);
+      add += 2; if (add == 6) add = 2;
+    }
+    if ((mpz_cmp_ui(nn, 1) > 0) &&
+        ((mpz_cmp_ui(b, 0) == 0) || (mpz_cmp(nn, b) <= 0)))
+    {
+      setListEntry(primes, index, nn);
+      multiplicities[index++] = 1;
+      mpz_set_ui(nn, 1);
+    }
   }
 
@@ -265 +305 @@
   lists L=(lists)omAllocBin(slists_bin);
   L->Init(4);
+  if (positive==-1) mpz_neg(nn,nn);
   setListEntry(L, 0, nn);
   L->m[1].rtyp = LIST_CMD; L->m[1].data = (void*)primesL;