tfm/ltm relation

[minad]

I think this has been discussed before. I've seen tfm also considers adding multi precision ints.

Another approach I find interesting is the one gmp takes where ones high-level and low-level functions (which take pre allocated digits as arguments).

Is there some plan on how things will evolve in the future?

[minad]

Some questions:

• Is there some list of software which uses tfm like you made for ltm?
• How does code quality compare, maybe tfm has some improvements due to lessons learned.
• Testing/test coverage
• Maybe it is possible to just import a few of the fast functions into ltm?
• Tfm contains asm in contrast to ltm?

[sjaeckel]

Is there some plan on how things will evolve in the future?

No, there's no real plan.

The original idea was to merge ltm into tfm, then reality happened and now ltm has evolved a lot and we should probably think about merging tfm's optimizations into ltm.

Is there some list of software which uses tfm like you made for ltm?

No, there's no list. The ones that come immediately to my mind are ClamAV and libtomcrypt

[minad]

@sjaeckel I updated the list of questions I am having.

[sjaeckel]

• How does code quality compare, maybe tfm has some improvements due to lessons learned.

I'd say it's similar

• Testing/test coverage

not that good

• Maybe it is possible to just import a few of the fast functions into ltm?

definitely possible

• Tfm contains asm in contrast to ltm?

yes, that's where the "fast" comes from ... but it's not maintained ... e.g. ClamAV uses the plain C version of tfm w/o asm

[minad]

So the algorithms and representation are the same (60 bits of 64 bits etc)? Since I think this is sth where gmp differs for example. They work with the full width afaik.
So the plain c part should be mostly equivalent to ltm with the difference of not allocating?

[sjaeckel]

So the algorithms

tfm has less operations & algorithms implemented

and representation are the same (60 bits of 64 bits etc)?

No, tfm uses the full width.

So the plain c part should be mostly equivalent to ltm with the difference of not allocating?

operation-wise it was equivalent up to some point where ltm started to get more people working on it.

[minad]

@sjaeckel Regarding #420 I looked a bit into the comba multiplier, since this is the one restricting ltm to 60 bits. It seems to me that the restriction is possible to lift as is done in fp_mul_comba. Instead of _W, there three fp_digits c0, c1, c2 are used.

So if one wants to import some of the fast functions to ltm one should at first lift the MP_DIGIT_BIT restriction. Basically the fast functions are comba loop unrolling + primitives in assembly.

Ping @czurnieden

[justinethier]

The original idea was to merge ltm into tfm, then reality happened and now ltm has evolved a lot and we should probably think about merging tfm's optimizations into ltm.

It would be great if there are optimizations that can be merged into ltm. Do you think any significant speedups are possible?

[minad]

It would be great if there are optimizations that can be merged into ltm. Do you think any significant speedups are possible?

As far as I see it there are speedups of maybe factor 2 for multiplication etc, since tfm uses some unrolled implementations in that case. Look here for some encryption benchmark graphs #447.

However merging the libraries is not trivial since they are relying on different integer representations. I did some preparatory experiments to unify the representations in #447 but I have given up on that for now.

Do you have specific performance issues with the library as of now? Unrelated question, do you use an unboxed representation for small integers in your scheme implementation?

[justinethier]

No specific performance issues, but Cyclone performs poorly on the bigint benchmarks pi and chudnovsky. The latest ltm release did help a bit in this regard.

Overall I like ltm and your licensing terms and prefer to keep using this library, especially if there will be more performance enhancements going forward. I understand it is unlikely to ever be as fast as gmp, though.

Yes, unboxed integers are used when the values are small enough.

[minad]

@justinethier I wonder what other scheme implementations use if they perform better. GMP or some custom implementation? If they are using custom implementations it would be interesting to know, since we might be able to improve some things here. But competing with GMP is out of the question.

[justinethier]

Apparently Gambit and Chicken use custom bignum implementations.

There is a series of articles on the new Chicken 5 implementation that may be of interest:
https://www.more-magic.net/posts/numeric-tower-part-2.html

Not sure how helpful this would be:
https://github.com/gambit/gambit/blob/c65e6b33d2d81e7abc4df35c6d49ecce52d7930f/lib/_num.scm#L5546