Big Integer

[koba-e964]

The library of big integer operations.

Description

make-bigint : Creates a bigint. It accepts integers and strings. bigint-add, bigint-sub, bigint-mul, bigint-div, bigint-rem : Operations. Quotients are truncated toward 0. The signs of remainders are equal to those of dividends. bigint-add!, bigint-sub!, bigint-mul! : In-place operations. The results are written to the first arguments. bigint->number : Converts the argument to a double. bigint->string : Converts the argument to a string. bigint-underlying : Returns the underlying vector of the given bigint.

Every pure operation other than make-bigint accepts either integers or bigints. The first argument of in-place operations must be a bigint.

[koba-e964]

Currently I have a hard time fixing bugs somewhere, which cause calculation of large numbers (about 170 decimal digits) wrong. I suppose that my code doesn't work with gc well, because I don't know picrin's gc very much.

[koba-e964]

make test-big-number in https://github.com/picrin-scheme/picrin/pull/305/commits/a1d9cd6c4395563ec8959fb1f18d7c37ffb614fa fails. When I run the interpreter and call bigint->string for a large number, something will break and assertion failure or segfault or something might happen.

[nyuichi]

Aw, does that segfault? That should be picrin's fault. I'll check it out.

[koba-e964]

Thanks. I found that if gc was turned off (by modifying pic_gc() in extlib/benz/gc.c), everything (tests, repl) worked well. My code doesn't work with picrin's gc, but I don't know why.

[koba-e964]

I wrote everything worked well, but Travis CI failed because of memory exhaustion...

[koba-e964]

Looks like something is wrong with bitmap gc (#define PIC_BITMAP_GC 0 in extlib/benz/include/picrin/setup.h made the test pass).

[koba-e964]

Given n-bit integer, bigint->string will create n^2/2 objects due to naive division. (if n=500, it will call pic_make_vec more than 120,000 times) That might be the cause of this problem.

[KeenS]

Is it possible to write in-place version of division like gmp, say,

bigint_vec_div_ip1(pic_state *pic, const pic_value *v1, const pic_value v2, pic_value *rem);
bigint_vec_div_ip2(pic_state *pic, const pic_value v1, const pic_value *v2, pic_value *quo);

?

[koba-e964]

digits in pic_bigint_t is meant to be immutable, so I think we cannot have any in-place operations for vectors. (we cannot modify existing vectors for bigints). vectors representing integers should have the non-zero most significant digit and vectors' length cannot be changed, so in-place operations will cause problems.