3 ms·

Very useful post! Also it's cool to see how many people in this thread have worked on this problem -- lots of new info here I haven't seen I wonder if anyone

by chubot 2y ago

Very useful post! Also it's cool to see how many people in this thread have worked on this problem -- lots of new info here I haven't seen I wonder if anyone is interested in implementing a big numbers in Oils? It's a Unix shell with TWO complete implementations - the "executable spec" in Python, and an automatic translation to pure C++ (which is 30x-50x faster) We currently use 64-bit integers in C++, but big nums are a better semantic. Some trivia about bad shell semantics here: Integers - Don't do whatever Python or C++ does - https://www.oilshell.org/blog/2024/03/release-0.21.0.html#integers-dont-do-whatever-python-or-c-does https://www.oilshell.org/blog/2024/03/release-0.21.0.html#in... This is a very self-contained project: the interface is defined by 200 lines of Python: https://github.com/oilshell/oil/blob/master/mycpp/mops.py https://github.com/oilshell/oil/blob/master/mycpp/mops.py and the trivial 64-bit overflowing implementation is also about 200 lines: https://github.com/oilshell/oil/blob/master/mycpp/gc_mops.h https://github.com/oilshell/oil/blob/master/mycpp/gc_mops.h https://github.com/oilshell/oil/blob/master/mycpp/gc_mops.cc https://github.com/oilshell/oil/blob/master/mycpp/gc_mops.cc (We have a fast Ninja-based build system, so you can probably iterate on this in 100 milliseconds or less -- it should be fun for the right person) --- I think the main reason it is specific to Oils is that the bigger number should become GC objects. Details on our GC here: Pictures of a Working Garbage Collector - https://www.oilshell.org/blog/2023/01/garbage-collector.html https://www.oilshell.org/blog/2023/01/garbage-collector.html It's been very solid for the last 18 months, basically because it's well tested by ASAN and #ifdef testing modes. The main thing I'd be concerned with is how to TEST that big number operations are correct. I think there are probably some interesting strategies, which I'd love to discuss. You're of course welcome to adapt existing open source code, including code you've already written -- I probably even prefer that, i.e. something that has had some real world testing. We want all the operations in that file, and it should be integrated with our GC. --- We've had ~6 contributors funded by grants from https://nlnet.nl https://nlnet.nl for the past couple years, so you can even be paid (there's a chance it depends on the country you live in, but generally a wide range of situations is OK). Contact me at andy at oilshell.org or https://oilshell.zulipchat.com/ https://oilshell.zulipchat.com/ if interested!

JonChesterfield 2y ago
It doesn't look especially specific to me - slightly hack the structure in https://github.com/libtom/libtommath https://github.com/libtom/libtommath to make sense to your garbage collector and you're pretty much done. That somewhat punts on the testing question but I doubt add/mul/bitops from that library are buggy.
- chubot 2y ago
  Hm I'm not familiar with that library (or really any others in the landscape). Why pick that one? Why be doubtful it's buggy -- is it used in a major app? I can't really tell from this page: https://www.libtom.net/LibTomMath/ https://www.libtom.net/LibTomMath/ I'd be interested in a review / survey of different options, and the strategy for testing. Basically the tests should "argue" that the code is correct, and documentation / blog posts also count! (I'm honestly not sure how hard it is to make a correct big num library. But I think the original article in this series said there were probably bugs, so I'm guessing it's not trivial) To give a flavor, we publish test results and and coverage numbers like this [1], and any new library should be consistent with this: https://www.oilshell.org/release/0.22.0/quality.html https://www.oilshell.org/release/0.22.0/quality.html Our GC runtime has less than 5000 lines of hand-written C++ now, so any solution should be in proportion to that. That is, we probably wouldn't take on 3000 lines of code just for big nums. So we favor correctness over performance. Hopefully there would be little perf loss in the small int case, but it's OK if the big int case is slow. It's the rarer case for sure. It's a shell, not a Fortran competitor! --- As far as the grant, we pay in 2500 euro or 5000 euro increments, and I don't try to parse "effort spent" any more than that. I care about the result, not if it's easy for a particular person :) For example earlier this year we had a contributor Justin who worked on the pretty printer, with Wadler's algorithm (which I was unfamiliar with). https://www.oilshell.org/blog/2024/06/release-0.22.0.html https://www.oilshell.org/blog/2024/06/release-0.22.0.html And he had co-authored a paper on pretty printing, so it was probably not too difficult overall. But that's a good thing as far as I'm concerned! So if you or anyone else thinks it's easy, please feel free to contact me / play around with the code, etc. https://github.com/oilshell/oil/wiki/Where-Contributors-Have-Problems https://github.com/oilshell/oil/wiki/Where-Contributors-Have... [1] our unit test coverage is reported at 83% or so, but we favor "exterior" tests, so it's really close to 95% or 99%. Also of course line coverage isn't really a way to measure correctness per se.

by chubot 2y ago

JonChesterfield 2y ago

It doesn't look especially specific to me - slightly hack the structure in https://github.com/libtom/libtommath https://github.com/libtom/libtommath to make sense to your garbage collector and you're pretty much done. That somewhat punts on the testing question but I doubt add/mul/bitops from that library are buggy.

chubot 2y ago
Hm I'm not familiar with that library (or really any others in the landscape). Why pick that one? Why be doubtful it's buggy -- is it used in a major app? I can't really tell from this page: https://www.libtom.net/LibTomMath/ https://www.libtom.net/LibTomMath/ I'd be interested in a review / survey of different options, and the strategy for testing. Basically the tests should "argue" that the code is correct, and documentation / blog posts also count! (I'm honestly not sure how hard it is to make a correct big num library. But I think the original article in this series said there were probably bugs, so I'm guessing it's not trivial) To give a flavor, we publish test results and and coverage numbers like this [1], and any new library should be consistent with this: https://www.oilshell.org/release/0.22.0/quality.html https://www.oilshell.org/release/0.22.0/quality.html Our GC runtime has less than 5000 lines of hand-written C++ now, so any solution should be in proportion to that. That is, we probably wouldn't take on 3000 lines of code just for big nums. So we favor correctness over performance. Hopefully there would be little perf loss in the small int case, but it's OK if the big int case is slow. It's the rarer case for sure. It's a shell, not a Fortran competitor! --- As far as the grant, we pay in 2500 euro or 5000 euro increments, and I don't try to parse "effort spent" any more than that. I care about the result, not if it's easy for a particular person :) For example earlier this year we had a contributor Justin who worked on the pretty printer, with Wadler's algorithm (which I was unfamiliar with). https://www.oilshell.org/blog/2024/06/release-0.22.0.html https://www.oilshell.org/blog/2024/06/release-0.22.0.html And he had co-authored a paper on pretty printing, so it was probably not too difficult overall. But that's a good thing as far as I'm concerned! So if you or anyone else thinks it's easy, please feel free to contact me / play around with the code, etc. https://github.com/oilshell/oil/wiki/Where-Contributors-Have-Problems https://github.com/oilshell/oil/wiki/Where-Contributors-Have... [1] our unit test coverage is reported at 83% or so, but we favor "exterior" tests, so it's really close to 95% or 99%. Also of course line coverage isn't really a way to measure correctness per se.