diff options
| -rw-r--r-- | core/math/big/basic.odin | 26 | ||||
| -rw-r--r-- | core/math/big/build.bat | 6 | ||||
| -rw-r--r-- | core/math/big/common.odin | 2 | ||||
| -rw-r--r-- | core/math/big/example.odin | 23 |
4 files changed, 34 insertions, 23 deletions
diff --git a/core/math/big/basic.odin b/core/math/big/basic.odin index 226ddc068..cf641c029 100644 --- a/core/math/big/basic.odin +++ b/core/math/big/basic.odin @@ -580,9 +580,8 @@ int_mul :: proc(dest, src, multiplier: ^Int) -> (err: Error) { /*
Early out for `multiplier` is zero; Set `dest` to zero.
*/
- if z, _ := is_zero(multiplier); z {
- return zero(dest);
- }
+ if z, _ := is_zero(multiplier); z { return zero(dest); }
+ if z, _ := is_zero(src); z { return zero(dest); }
if src == multiplier {
/*
@@ -748,6 +747,10 @@ int_sqrmod :: proc(remainder, number, modulus: ^Int) -> (err: Error) { sqrmod :: proc { int_sqrmod, };
+/*
+ TODO: Use Sterling's Approximation to estimate log2(N!) to size the result.
+ This way we'll have to reallocate less, possibly not at all.
+*/
int_factorial :: proc(res: ^Int, n: DIGIT) -> (err: Error) {
if n < 0 || n > _FACTORIAL_MAX_N || res == nil { return .Invalid_Argument; }
@@ -759,12 +762,7 @@ int_factorial :: proc(res: ^Int, n: DIGIT) -> (err: Error) { return int_factorial_binary_split(res, n);
}
- a := &Int{};
- defer destroy(a);
-
- if err = set( a, i - 1); err != .None { return err; }
if err = set(res, _factorial_table[i - 1]); err != .None { return err; }
-
for {
if err = mul(res, res, DIGIT(i)); err != .None || i == n { return err; }
i += 1;
@@ -1168,12 +1166,12 @@ _int_mul_comba :: proc(dest, a, b: ^Int, digits: int) -> (err: Error) { old_used := dest.used;
dest.used = pa;
- for ix = 0; ix < pa; ix += 1 {
- /*
- Now extract the previous digit [below the carry].
- */
- dest.digit[ix] = W[ix];
- }
+ /*
+ Now extract the previous digit [below the carry].
+ */
+ // for ix = 0; ix < pa; ix += 1 { dest.digit[ix] = W[ix]; }
+
+ copy_slice(dest.digit[0:], W[:pa]);
/*
Clear unused digits [that existed in the old copy of dest].
diff --git a/core/math/big/build.bat b/core/math/big/build.bat index d454fef4d..2c1edfcec 100644 --- a/core/math/big/build.bat +++ b/core/math/big/build.bat @@ -1,10 +1,10 @@ @echo off
-:odin run . -vet
+odin run . -vet
: -o:size -no-bounds-check
:odin build . -build-mode:shared -show-timings -o:minimal -use-separate-modules
:odin build . -build-mode:shared -show-timings -o:size -use-separate-modules -no-bounds-check
:odin build . -build-mode:shared -show-timings -o:size -use-separate-modules
-odin build . -build-mode:shared -show-timings -o:speed -use-separate-modules -no-bounds-check
+:odin build . -build-mode:shared -show-timings -o:speed -use-separate-modules -no-bounds-check
:odin build . -build-mode:shared -show-timings -o:speed -use-separate-modules
-python test.py
\ No newline at end of file +:python test.py
\ No newline at end of file diff --git a/core/math/big/common.odin b/core/math/big/common.odin index bcda658b0..5a51c7405 100644 --- a/core/math/big/common.odin +++ b/core/math/big/common.odin @@ -45,7 +45,7 @@ _MAX_ITERATIONS_ROOT_N :: 500; /* Largest `N` for which we'll compute `N!` */ -_FACTORIAL_MAX_N :: 100_000; +_FACTORIAL_MAX_N :: 1_000_000; /* Cutoff to switch to int_factorial_binary_split, and its max recursion level. diff --git a/core/math/big/example.odin b/core/math/big/example.odin index 10a14507f..7c2df9303 100644 --- a/core/math/big/example.odin +++ b/core/math/big/example.odin @@ -111,17 +111,30 @@ print :: proc(name: string, a: ^Int, base := i8(10), print_name := false, newlin } demo :: proc() { - err: Error; + as: string; + defer delete(as); + a, b, c, d, e, f := &Int{}, &Int{}, &Int{}, &Int{}, &Int{}, &Int{}; defer destroy(a, b, c, d, e, f); + N :: 5_000; + s := time.tick_now(); - err = choose(a, 65535, 255); - Timings[.choose].t += time.tick_since(s); Timings[.choose].c += 1; + err = factorial(a, N); + Timings[.factorial].t += time.tick_since(s); Timings[.factorial].c += 1; + if err != .None { + fmt.printf("factorial(%v) returned %v\n", N, err); + } + + s = time.tick_now(); + as, err = itoa(a, 16); + Timings[.itoa].t += time.tick_since(s); Timings[.itoa].c += 1; + if err != .None { + fmt.printf("itoa(factorial(%v), 16) returned %v\n", N, err); + } - print("65535 choose 255", a, 10, true, true, true); - fmt.printf("Error: %v\n", err); + fmt.printf("factorial(%v): %v (first 10 hex digits)\n", N, as[:10]); } main :: proc() { |