picrin

picrin copied to clipboard

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.

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.

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.

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

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.

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

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

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.

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);

?

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.