GNOME.org
 

[gnumeric] NT_OMEGA: New function.

commit 67e68a8e5482c260c7d40431fa64b40b658e4347
Author: Morten Welinder <terra gnome org>
Date:   Fri Apr 12 12:12:06 2013 -0400

    NT_OMEGA: New function.

 NEWS                               |    1 +
 doc/C/func.defs                    |    8 ++++
 doc/C/functions.xml                |   33 ++++++++++++++++
 plugins/fn-numtheory/ChangeLog     |    6 +++
 plugins/fn-numtheory/numtheory.c   |   73 +++++++++++++++++++++++++++---------
 plugins/fn-numtheory/plugin.xml.in |    1 +
 6 files changed, 104 insertions(+), 18 deletions(-)
---
diff --git a/NEWS b/NEWS
index 7826a0d..950c95a 100644
--- a/NEWS
+++ b/NEWS
@@ -34,6 +34,7 @@ Morten:
        * Fix saving of certain XL2007 functions like IFERROR.
        * Ensure full precision for complex numbers.  [#697634]
        * Fix parsing of 'Sheet1!#REF!' as used by XL.  [#683494]
+       * New function NT_OMEGA.
 
 --------------------------------------------------------------------------
 Gnumeric 1.12.1
diff --git a/doc/C/func.defs b/doc/C/func.defs
index 20dfb7e..2f0abd2 100644
--- a/doc/C/func.defs
+++ b/doc/C/func.defs
@@ -3872,6 +3872,14 @@ Strings and empty cells are simply ignored.
 @SEEALSO=ITHPRIME,NT_PHI,NT_SIGMA,NT_D
 
 @CATEGORY=Number Theory
+ FUNCTION=NT_OMEGA
+ SHORTDESC=Numer of distinct prime factors
+ SYNTAX=NT_OMEGA(n)
+ ARGUMENTDESCRIPTION=@{n}: positive integer
+ NOTE=Returns the number of distinct prime factors without multiplicity.
+ SEEALSO=NT_D,ITHPRIME,NT_SIGMA
+
+ CATEGORY=Number Theory
 @FUNCTION=NT_PHI
 @SHORTDESC=Euler's totient function
 @SYNTAX=NT_PHI(n)
diff --git a/doc/C/functions.xml b/doc/C/functions.xml
index 461144c..d466a61 100644
--- a/doc/C/functions.xml
+++ b/doc/C/functions.xml
@@ -13255,6 +13255,39 @@
       </para>
       </refsect1>
     </refentry>
+    <refentry id="gnumeric-function-NT_OMEGA">
+      <refmeta>
+        <refentrytitle>
+          <function>NT_OMEGA</function>
+        </refentrytitle>
+      </refmeta>
+      <refnamediv>
+        <refname>
+          <function>NT_OMEGA</function>
+        </refname>
+        <refpurpose>
+        Numer of distinct prime factors
+      </refpurpose>
+      </refnamediv>
+      <refsynopsisdiv>
+        <synopsis><function>NT_OMEGA</function>(<parameter>n</parameter>)</synopsis>
+      </refsynopsisdiv>
+      <refsect1>
+        <title>Arguments</title>
+        <para><parameter>n</parameter>: positive integer</para>
+      </refsect1>
+      <refsect1>
+        <title>Note</title>
+        <para>Returns the number of distinct prime factors without multiplicity.</para>
+      </refsect1>
+      <refsect1>
+        <title>See also</title>
+        <para><link linkend="gnumeric-function-NT_D"><function>NT_D</function></link>,
+        <link linkend="gnumeric-function-ITHPRIME"><function>ITHPRIME</function></link>,
+        <link linkend="gnumeric-function-NT_SIGMA"><function>NT_SIGMA</function></link>.
+      </para>
+      </refsect1>
+    </refentry>
     <refentry id="gnumeric-function-NT_PHI">
       <refmeta>
         <refentrytitle>
diff --git a/plugins/fn-numtheory/ChangeLog b/plugins/fn-numtheory/ChangeLog
index b8c72ce..b605444 100644
--- a/plugins/fn-numtheory/ChangeLog
+++ b/plugins/fn-numtheory/ChangeLog
@@ -1,3 +1,9 @@
+2013-04-12  Morten Welinder  <terra gnome org>
+
+       * numtheory.c (ithprime): Minor speed-up.  Increase limit to 10^7
+       primes.
+       (gnumeric_nt_omega): New function.
+
 2013-03-09  Morten Welinder <terra gnome org>
 
        * Release 1.12.1
diff --git a/plugins/fn-numtheory/numtheory.c b/plugins/fn-numtheory/numtheory.c
index 1ad6173..7ef112a 100644
--- a/plugins/fn-numtheory/numtheory.c
+++ b/plugins/fn-numtheory/numtheory.c
@@ -62,47 +62,48 @@ intpow (int p, int v)
        return (v % 2) ? temp * p : temp;
 }
 
-#define ITHPRIME_LIMIT (1 << 22)
-static gint *prime_table = NULL;
+#define ITHPRIME_LIMIT 10000000
+static guint *prime_table = NULL;
 
 /* Calculate the i-th prime.  Returns TRUE on error.  */
 static gboolean
 ithprime (int i, guint64 *res)
 {
-       static int computed = 0;
-       static int allocated = 0;
+       static guint computed = 0;
+       static guint allocated = 0;
 
-       if (i < 1 || i > ITHPRIME_LIMIT)
+       if (i < 1 || (guint)i > ITHPRIME_LIMIT)
                return TRUE;
 
-       if (i > computed) {
-               int candidate;
+       if ((guint)i > computed) {
+               static guint candidate = 3;
+               static guint jlim = 1;
 
-               if (i > allocated) {
-                       allocated = MAX (i, 2 * allocated + 100);
+               if ((guint)i > allocated) {
+                       allocated = MAX ((guint)i, 2 * allocated + 100);
                        allocated = MIN (allocated, ITHPRIME_LIMIT);
-                       prime_table = g_renew (int, prime_table, allocated);
+                       prime_table = g_renew (guint, prime_table, allocated);
                        if (computed == 0) {
                                prime_table[computed++] = 2;
                                prime_table[computed++] = 3;
                        }
                }
 
-               candidate = prime_table[computed - 1];
-               /*
-                * Note, that the candidate is odd since we filled in the first
-                * two prime numbers.
-                */
-               while (i > computed) {
+               while ((guint)i > computed) {
                        gboolean prime = TRUE;
-                       int j;
+                       guint j;
+
                        candidate += 2;  /* Skip even candidates.  */
 
-                       for (j = 1; prime_table[j] * prime_table[j] <= candidate; j++)
+                       while (candidate >= prime_table[jlim] * prime_table[jlim])
+                               jlim++;
+
+                       for (j = 1; j < jlim; j++) {
                                if (candidate % prime_table[j] == 0) {
                                        prime = FALSE;
                                        break;
                                }
+                       }
 
                        if (prime)
                                prime_table[computed++] = candidate;
@@ -214,6 +215,39 @@ isprime (guint64 n)
 
 /* ------------------------------------------------------------------------- */
 
+static GnmFuncHelp const help_nt_omega[] = {
+       { GNM_FUNC_HELP_NAME, F_("NT_OMEGA:Numer of distinct prime factors")},
+       { GNM_FUNC_HELP_ARG, F_("n:positive integer")},
+       { GNM_FUNC_HELP_NOTE, F_("Returns the number of distinct prime factors without multiplicity.") },
+       { GNM_FUNC_HELP_EXAMPLES, "=NT_PHI(9)" },
+       { GNM_FUNC_HELP_SEEALSO, "NT_D,ITHPRIME,NT_SIGMA"},
+       { GNM_FUNC_HELP_END }
+};
+
+static void
+walk_for_omega (guint64 p, int v, void *data_)
+{
+       int *data = data_;
+       (*data)++;
+}
+
+static GnmValue *
+gnumeric_nt_omega (GnmFuncEvalInfo *ei, GnmValue const * const *args)
+{
+       int omega = 0;
+       gnm_float n = gnm_floor (value_get_as_float (args[0]));
+
+       if (n < 1 || n > bit_max)
+               return value_new_error_NUM (ei->pos);
+
+       if (walk_factorization ((guint64)n, &omega, walk_for_omega))
+               return value_new_error (ei->pos, OUT_OF_BOUNDS);
+
+       return value_new_int (omega);
+}
+
+/* ------------------------------------------------------------------------- */
+
 static GnmFuncHelp const help_phi[] = {
        { GNM_FUNC_HELP_NAME, F_("NT_PHI:Euler's totient function")},
        { GNM_FUNC_HELP_ARG, F_("n:positive integer")},
@@ -646,6 +680,9 @@ const GnmFuncDescriptor num_theory_functions[] = {
        {"pfactor", "f", help_pfactor,
         &gnumeric_pfactor, NULL, NULL, NULL,
         GNM_FUNC_SIMPLE, GNM_FUNC_IMPL_STATUS_UNIQUE_TO_GNUMERIC, GNM_FUNC_TEST_STATUS_NO_TESTSUITE },
+       {"nt_omega",   "f", help_nt_omega,
+        &gnumeric_nt_omega,  NULL, NULL, NULL,
+        GNM_FUNC_SIMPLE, GNM_FUNC_IMPL_STATUS_UNIQUE_TO_GNUMERIC, GNM_FUNC_TEST_STATUS_NO_TESTSUITE },
        {"nt_phi",   "f", help_phi,
         &gnumeric_phi,      NULL, NULL, NULL,
         GNM_FUNC_SIMPLE, GNM_FUNC_IMPL_STATUS_UNIQUE_TO_GNUMERIC, GNM_FUNC_TEST_STATUS_NO_TESTSUITE },
diff --git a/plugins/fn-numtheory/plugin.xml.in b/plugins/fn-numtheory/plugin.xml.in
index 86c0a02..ae0705e 100644
--- a/plugins/fn-numtheory/plugin.xml.in
+++ b/plugins/fn-numtheory/plugin.xml.in
@@ -15,6 +15,7 @@
                                <function name="ithprime"/>
                                <function name="nt_d"/>
                                <function name="nt_mu"/>
+                               <function name="nt_omega"/>
                                <function name="nt_phi"/>
                                <function name="nt_pi"/>
                                <function name="nt_sigma"/>
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]