summaryrefslogtreecommitdiffstats
path: root/ml/dlib/dlib/test/bigint.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'ml/dlib/dlib/test/bigint.cpp')
-rw-r--r--ml/dlib/dlib/test/bigint.cpp522
1 files changed, 522 insertions, 0 deletions
diff --git a/ml/dlib/dlib/test/bigint.cpp b/ml/dlib/dlib/test/bigint.cpp
new file mode 100644
index 000000000..3ddc631b4
--- /dev/null
+++ b/ml/dlib/dlib/test/bigint.cpp
@@ -0,0 +1,522 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+
+
+#include <sstream>
+#include <string>
+
+#include <dlib/bigint.h>
+
+#include "tester.h"
+
+namespace
+{
+ using namespace test;
+ using namespace dlib;
+ using namespace std;
+
+ logger dlog("test.bigint");
+
+ namespace bigint_kernel_test_helpers
+ {
+ template <
+ typename bint
+ >
+ bint short_fact (unsigned short value)
+ /*!
+ ensures
+ - returns the factorial of value
+ !*/
+ {
+ using namespace relational_operators;
+
+ bint a = 1;
+ for (unsigned short i = 2; i <= value; ++i)
+ a *= i;
+
+ return a;
+ }
+
+ template <
+ typename bint
+ >
+ bint short_fact_squared (unsigned short value)
+ /*!
+ ensures
+ - returns the square of the factorial of value
+ !*/
+ {
+ using namespace relational_operators;
+
+ bint a = 1;
+ for (unsigned short i = 2; i <= value; ++i)
+ {
+ a *= i;
+ a *= i;
+ }
+
+ return a;
+ }
+
+
+ template <
+ typename bint
+ >
+ bint big_fact (unsigned short value)
+ /*!
+ ensures
+ - returns the factorial of value
+ !*/
+ {
+ using namespace relational_operators;
+
+ bint a = 1;
+ int k = 0;
+ for (bint i = 2; i <= value; ++i)
+ {
+ ++k;
+ if (k%10 == 0)
+ print_spinner();
+ a *= i;
+ }
+
+ return a;
+ }
+ }
+
+ template <
+ typename bint
+ >
+ void bigint_kernel_test (
+ )
+ /*!
+ requires
+ - bint is an implementation of bigint/bigint_kernel_abstract.h
+ ensures
+ - runs tests on bint for compliance with the specs
+ !*/
+ {
+ using namespace bigint_kernel_test_helpers;
+ using namespace relational_operators;
+ istringstream sin;
+ ostringstream sout;
+
+ bint i = 0;
+ bint a(5), b, c(0);
+
+ DLIB_TEST(5 - a == 0);
+ DLIB_TEST(a - 5 == 0);
+
+ DLIB_TEST(0 - c == 0);
+ DLIB_TEST(c - 0 == 0);
+
+ DLIB_TEST(0 + c == 0);
+ DLIB_TEST(c + 0 == 0);
+
+ DLIB_TEST(0 + a == 5);
+ DLIB_TEST(a + 0 == 5);
+
+ DLIB_TEST(0 - b == 0);
+ DLIB_TEST(b - 0 == 0);
+
+ DLIB_TEST(0 + b == 0);
+ DLIB_TEST(b + 0 == 0);
+
+ DLIB_TEST(i == 0);
+ DLIB_TEST(a == 5);
+ DLIB_TEST(b == 0);
+ DLIB_TEST(c == 0);
+
+
+
+ a -= 5;
+ DLIB_TEST(a == 0);
+
+
+
+ for (int k = 0; k < 100; ++k)
+ {
+ // compute the factorial of k using the O(n) multiplication algorithm
+ a = short_fact<bint>(k);
+ // compute the factorial of k using the full blown big int
+ // multiplication algorithm.
+ b = big_fact<bint>(k);
+ // compute the square of the factorial of k using the full blown
+ // big int multiplication algorithm.
+ c = a*b;
+ // make sure a and b ended up being the same number
+ DLIB_TEST_MSG(a == b,
+ "k: " << k << "\n"
+ "short_fact: " << a << "\n"
+ "big_fact: " << b
+ );
+ // make sure c really is the square of the factorial of k
+ DLIB_TEST_MSG(short_fact_squared<bint>(k) == c,"k: " << k);
+ print_spinner();
+ }
+
+ // do the same thing as the last loop but do it with way bigger numbers
+ for (int k = 1000; k < 10000; k += 2000)
+ {
+ bint a = short_fact<bint>(k);
+ bint b = big_fact<bint>(k);
+ bint c = a*b;
+ DLIB_TEST_MSG(a == b,
+ "k: " << k << "\n"
+ "short_fact: " << a << "\n"
+ "big_fact: " << b
+ );
+ DLIB_TEST_MSG(short_fact_squared<bint>(k) == c,"k: " << k);
+ print_spinner();
+ }
+
+
+
+ // test the << and >> operators a little
+ a = big_fact<bint>(20);
+ sout << a;
+ DLIB_TEST_MSG( sout.str() == "2432902008176640000","was: " << a);
+
+ sin.str("684626312793279327952039475203945");
+ sin >> a;
+ sout.str("");
+ sout << a;
+ DLIB_TEST(sout.str() == "684626312793279327952039475203945");
+
+ print_spinner();
+
+ DLIB_TEST(a > 0);
+
+
+ // make sure that when you try to read something that isn't a number
+ // into a bigint you get an error
+ DLIB_TEST(sin.fail() == false);
+ sin.str("the cat ate some cheese");
+ sin >> a;
+ DLIB_TEST(sin.fail() == true);
+ sin.clear();
+ sin.str("");
+
+
+
+ sin.str("3628913");
+ sin >> i;
+ DLIB_TEST(short_fact<bint>(10) + short_fact<bint>(5) - 7 == i);
+
+ sin.str("2432902008173011193");
+ sin >> i;
+ DLIB_TEST(short_fact<bint>(20) - short_fact<bint>(10) - 7 == i);
+
+ // test the serialization stuff
+ sout.str("");
+ serialize(i,sout);
+ i = 0;
+ sin.str(sout.str());
+ deserialize(i,sin);
+
+ DLIB_TEST(short_fact<bint>(20) - short_fact<bint>(10) - 7 == i);
+
+
+
+
+ print_spinner();
+
+
+
+
+ sin.str("100000");
+ sin >> b;
+ a = b;
+ ++b;
+ DLIB_TEST_MSG ( a + 1 == b,"a==" << a << endl << "b==" << b << endl);
+
+
+
+
+
+ // compute some stuff and see if you get the right value
+ a = 0;
+ b = 0;
+ sin.str("1000000");
+ sin >> b;
+ int mel = 0;
+ for (i = a; i <= b; ++i)
+ {
+ // switch it up on em
+ if (i%2 == 0)
+ a = a + i;
+ else
+ a += i;
+ ++mel;
+ if ((mel&0xFFF) == 0)
+ print_spinner();
+ }
+ DLIB_TEST_MSG(a == b*(b+1)/2, "a==" << a << endl << "b*(b+1)/2==" << b*(b+1)/2 << endl);
+
+
+
+
+
+
+ print_spinner();
+
+
+ // compute some stuff and see if you get the right value
+ // this time going the other way using operator--
+ a = 0;
+ b = 0;
+ sin.str("100000");
+ sin >> b;
+ i = b;
+ DLIB_TEST(i == b);
+ DLIB_TEST_MSG(i > 0,"i==" << i);
+ mel = 0;
+ for (i = b; i > 0; --i)
+ {
+ // switch it up on em
+ if (i%2 == 0)
+ a = a + i;
+ else
+ a += i;
+ ++mel;
+ if ((mel&0xFF) == 0)
+ print_spinner();
+ }
+ DLIB_TEST_MSG(a == b*(b+1)/2, "a==" << a << endl << "b*(b+1)/2==" << b*(b+1)/2 << endl);
+
+
+
+
+
+
+
+
+
+
+
+ DLIB_TEST(short_fact<bint>(10)/short_fact<bint>(5) == 30240);
+ DLIB_TEST(short_fact<bint>(10)/(short_fact<bint>(5)+1) == 29990);
+
+ sin.str("221172909834240000");
+ sin >> a;
+ DLIB_TEST(short_fact<bint>(20)/(short_fact<bint>(5)+1) == a/11);
+
+ sin.str("670442388044");
+ sin >> b;
+ DLIB_TEST(short_fact<bint>(20)/(short_fact<bint>(10)+1) == b);
+
+ print_spinner();
+
+ sin.str("1860479");
+ sin >> i;
+ DLIB_TEST_MSG(short_fact<bint>(20)/(short_fact<bint>(15)+1) == i,short_fact<bint>(20)/(short_fact<bint>(15)+1));
+
+ // test the serialization stuff
+ sout.str("");
+ serialize(i,sout);
+ i = 0;
+ sin.str(sout.str());
+ deserialize(i,sin);
+
+ DLIB_TEST_MSG(short_fact<bint>(20)/(short_fact<bint>(15)+1) == i,short_fact<bint>(20)/(short_fact<bint>(15)+1));
+
+
+ print_spinner();
+
+ // test the serialization stuff
+ sout.str("");
+ i = 0;
+ serialize(i,sout);
+ i = 1234;
+ sin.str(sout.str());
+ deserialize(i,sin);
+ DLIB_TEST(i == 0);
+
+
+ DLIB_TEST(short_fact<bint>(10000)/short_fact<bint>(9999) == 10000);
+
+
+ DLIB_TEST(bint(5)%bint(1) == 0);
+ DLIB_TEST(bint(5)%bint(6) == 5);
+ DLIB_TEST(bint(25)%bint(6) == 1);
+ print_spinner();
+ DLIB_TEST(bint(354)%bint(123) == 108);
+ DLIB_TEST(bint(20)%(bint(10)) == 0);
+ DLIB_TEST(bint(20)%(bint(10)+1) == 9);
+
+ DLIB_TEST(bint(20)%(bint(15)+1) == 4);
+
+
+ DLIB_TEST(short_fact<bint>(10)%(short_fact<bint>(5)+2) == 32);
+
+ sin.str("2908082");
+ sin >> i;
+ DLIB_TEST(short_fact<bint>(15)%(short_fact<bint>(10)+2) == i);
+
+
+
+
+
+
+ // same as some of the above stuff but using big_fact
+
+ DLIB_TEST(big_fact<bint>(10)%(big_fact<bint>(5)+2) == 32);
+
+ sin.str("2908082");
+ sin >> i;
+ DLIB_TEST(big_fact<bint>(15)%(big_fact<bint>(10)+2) == i);
+
+
+ print_spinner();
+
+
+ DLIB_TEST(big_fact<bint>(10)/big_fact<bint>(5) == 30240);
+ DLIB_TEST(big_fact<bint>(10)/(big_fact<bint>(5)+1) == 29990);
+
+ sin.str("221172909834240000");
+ sin >> a;
+ DLIB_TEST(big_fact<bint>(20)/(big_fact<bint>(5)+1) == a/11);
+
+
+ sin.str("670442388044");
+ sin >> b;
+ DLIB_TEST(big_fact<bint>(20)/(big_fact<bint>(10)+1) == b);
+
+
+ sin.str("1860479");
+ sin >> i;
+ DLIB_TEST_MSG(big_fact<bint>(20)/(big_fact<bint>(15)+1) == i,big_fact<bint>(20)/(big_fact<bint>(15)+1));
+
+ DLIB_TEST(big_fact<bint>(100)/big_fact<bint>(99) == 100);
+
+
+
+
+ sout.str("");
+ sout << "148571596448176149730952273362082573788556996128468876694221686370498539309";
+ sout << "4065876545992131370884059645617234469978112000000000000000000000";
+ sin.str(sout.str());
+ sin >> a;
+
+ sout.str("");
+ sout << "933262154439441526816992388562667004907159682643816214685929638952175999932";
+ sout << "299156089414639761565182862536979208272237582511852109168640000000000000000";
+ sout << "000000";
+ sin.str(sout.str());
+ sin >> b;
+
+
+ sout.str("");
+ sout << "138656248189732152054159609718432247180282092567575172939636909224427929240";
+ sout << "834642263988043338170905744175653189424779336521852536242160190545537133916";
+ sout << "649622615351174407746524657461692702500613722228638559932561661493048332720";
+ sout << "6050692647868232055316807680000000000000000000000000000000000000000000";
+ sin.str(sout.str());
+ sin >> c;
+
+ DLIB_TEST_MSG(a*b == c,
+ "a*b: " << a*b <<
+ "\nc: " << c);
+
+
+ print_spinner();
+
+ i = 0;
+ mel = 0;
+ unsigned long j;
+ for (j = 0; i < bint(100000); ++j)
+ {
+ DLIB_TEST(i++ == bint(j));
+ ++mel;
+ if((mel&0xFF) == 0)
+ print_spinner();
+ }
+ DLIB_TEST(j == 100000);
+
+ i = 1234;
+
+ DLIB_TEST(i == 1234);
+ DLIB_TEST(i < 2345 );
+ DLIB_TEST(i > 0 );
+ DLIB_TEST(i > 123 );
+
+ DLIB_TEST(i != 1334);
+ DLIB_TEST(i <= 2345);
+ DLIB_TEST(i >= 0 );
+ DLIB_TEST(i >= 123 );
+ DLIB_TEST(i >= 1234);
+ DLIB_TEST(i <= 1234);
+
+
+ DLIB_TEST(1234 == i);
+ DLIB_TEST(2345 > i);
+ DLIB_TEST(0 < i);
+ DLIB_TEST(123 < i);
+
+ DLIB_TEST(1334 != i);
+ DLIB_TEST(2345 >= i);
+ DLIB_TEST(0 <= i);
+ DLIB_TEST(123 <= i);
+ DLIB_TEST(1234 <= i);
+ DLIB_TEST(1234 >= i);
+
+
+ a = big_fact<bint>(200);
+ b = big_fact<bint>(100);
+
+ DLIB_TEST(a > b);
+ DLIB_TEST(a != b);
+ DLIB_TEST(b < a);
+ DLIB_TEST(b != a);
+ DLIB_TEST(b <= a);
+ DLIB_TEST(a >= b);
+
+
+
+ a = 10000;
+ a = a*a*a*a; a = a*a; a = a*a;
+ b = 2;
+ DLIB_TEST((a/b)*b == a);
+
+ a = 10000*5;
+ a = a*a*a*a; a = a*a; a = a*a;
+ b = 5;
+ DLIB_TEST((a/b)*b == a);
+ }
+
+
+
+
+ class bigint_tester : public tester
+ {
+ public:
+ bigint_tester (
+ ) :
+ tester ("test_bigint",
+ "Runs tests on the bigint component.")
+ {}
+
+ void perform_test (
+ )
+ {
+ dlog << LINFO << "testing kernel_1a";
+ bigint_kernel_test<bigint::kernel_1a>();
+ print_spinner();
+
+ dlog << LINFO << "testing kernel_1a_c";
+ bigint_kernel_test<bigint::kernel_1a_c>();
+ print_spinner();
+
+ dlog << LINFO << "testing kernel_2a";
+ bigint_kernel_test<bigint::kernel_2a>();
+ print_spinner();
+
+ dlog << LINFO << "testing kernel_2a_c";
+ bigint_kernel_test<bigint::kernel_2a_c>();
+ print_spinner();
+
+ }
+ } a;
+
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-28 01:48:32 +0000