[gnumeric] NT_OMEGA: New function.
- From: Morten Welinder <mortenw src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gnumeric] NT_OMEGA: New function.
- Date: Fri, 12 Apr 2013 16:12:24 +0000 (UTC)
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]