Author: pfg
Date: Thu Mar 26 22:05:42 2015
New Revision: 1669455
URL: http://svn.apache.org/r1669455
Log:
Re-implement Calc's RAND() function using a variant of KISS PRNG.
George Marsaglia's KISS algorithm is a rather simple implementation
of a random number generator but it has interesting properties with
respect ot the traditional Mersenne Twister.
I used the 2011 32 bit Multiply-with-carry variant, with an
undetermined period which is known to be not less than 10^40000000;
it is known to pass all the statistical tests.
The Apache OpenOffice implementation uses an aggressive seeding
scheme based on the internal rtl_random functions, rendering the
function basically unpredictable. As a side effect it is also not
possible to specify a seed for repeatability. No claims are made
concerning crypto-safeness.
The specific adaption for Apache OpenOffice is:
Copyright 2015 Pedro Giffuni
All rights reserved.
Huge thanks to Steve Kargl for pointing me to the algorithm and
the late George Marsaglia for creating it in the first place.
Modified:
openoffice/trunk/main/sc/source/core/tool/interpr1.cxx
Modified: openoffice/trunk/main/sc/source/core/tool/interpr1.cxx
URL:
http://svn.apache.org/viewvc/openoffice/trunk/main/sc/source/core/tool/interpr1.cxx?rev=1669455&r1=1669454&r2=1669455&view=diff
==============================================================================
--- openoffice/trunk/main/sc/source/core/tool/interpr1.cxx (original)
+++ openoffice/trunk/main/sc/source/core/tool/interpr1.cxx Thu Mar 26 22:05:42
2015
@@ -40,6 +40,7 @@
#include <unotools/transliterationwrapper.hxx>
#include <rtl/ustring.hxx>
#include <rtl/logfile.hxx>
+#include <rtl/random.h>
#include <unicode/uchar.h>
#include "interpre.hxx"
@@ -71,9 +72,6 @@
#include "doubleref.hxx"
#include "queryparam.hxx"
-#include <boost/random/mersenne_twister.hpp>
-#include <boost/random/uniform_01.hpp>
-
#include <boost/math/special_functions/acosh.hpp>
#include <boost/math/special_functions/asinh.hpp>
#include <boost/math/special_functions/atanh.hpp>
@@ -1545,17 +1543,47 @@ void ScInterpreter::ScPi()
PushDouble(F_PI);
}
+#define SCRANDOMQ_SIZE 4194304
+static sal_uInt32 nScRandomQ[SCRANDOMQ_SIZE], nScCarry = 0;
-void ScInterpreter::ScRandom()
+// Multiply with Carry
+sal_uInt32
+b32MWC(void)
{
- RTL_LOGFILE_CONTEXT_AUTHOR( aLogger, "sc", "bst",
"ScInterpreter::ScRandom" );
+ sal_uInt32 t, x;
+ static int j = (SCRANDOMQ_SIZE - 1);
- boost::random::mt19937 ScGen(static_cast<unsigned int>(std::time(0)));
- static boost::uniform_01<boost::mt19937> ScZeroOne(ScGen);
-
- PushDouble(ScZeroOne());
+ j = (j + 1) & (SCRANDOMQ_SIZE - 1);
+ x = nScRandomQ[j];
+ t = (x << 28) + nScCarry;
+ nScCarry = (x >> 4) - (t < x);
+ return (nScRandomQ[j] = t - x);
}
+// Congruential
+#define CNG ( cng = 69069 * cng + 13579 )
+// Xorshift
+#define XS ( xs ^= (xs << 13), xs ^= (xs >> 17), xs ^= (xs << 5) )
+
+#define KISS (b32MWC() + CNG + XS)
+
+void ScInterpreter::ScRandom()
+{
+ RTL_LOGFILE_CONTEXT_AUTHOR( aLogger, "sc", "pfg",
"ScInterpreter::ScRandom" );
+
+ static rtlRandomPool aPool = rtl_random_createPool();
+ static sal_Bool SqSeeded = sal_False;
+ static sal_uInt32 i, x, cng, xs = 362436069;
+
+ // Seeding for the PRNG
+ if (SqSeeded == sal_False) {
+ rtl_random_getBytes(aPool, &cng, sizeof(cng));
+ rtl_random_getBytes(aPool, &nScRandomQ,
+ sizeof(nScRandomQ[0]) * SCRANDOMQ_SIZE);
+ SqSeeded = sal_True;
+ }
+ PushDouble(static_cast<double>(KISS) / SAL_MAX_UINT32);
+}
void ScInterpreter::ScTrue()
{
