11 ms·
LibBF – a small library to handle arbitrary precision floating point numbers
- deleted 9y ago[deleted]
- pettou 9y agoI don't see any changelog, does anyone know what's new since the last release?
- progval 9y agoAccording to the copyright notice, development started in 2017, so it is possibly the first release.
- slartibardfast0 9y agoMIT license makes this great for WebAssembly! Looking forward to benchmarking this in a wasm context.
- kodablah 9y agoLooking at the code this should be quite simple since libc is the only dep. You can Emscripten at first to be easy, but to wrap it up as a JS lib, you can probably implement the libc calls yourself easily and remove the Emscripten dep. The author even broke off bf_realloc to put your own alloc impl (which can be written in WASM, but I suggest writing it in C before the compilation).
- slartibardfast0 9y agocheers, sadly I won't be exploring JS lib wrapper approach. we're already deep down the EMSCRIPTEN_BINDINGS() rabbit-hole :) originally, the fixed size heap (/w optimisations) meant unbound use from a JS lib was too hard to reason about; hence avoided entirely in favour of a emscripten blackbox.
- GSGSGS 9y agoDo you have a link for this ?
- hint23 9y agoYou can already try LibBF online at http://numcalc.com http://numcalc.com
- danbruc 9y agoMostly off topic but maybe this post attracts people who know the answer to a question that I ran into when I implemented a big integer based rational number library some time ago. The decimal representation of a rational number p / q has the general form ±<integer part>.<non-repeating fractional part>(<repeating fractional part>), for example 41,111,111 / 333,000 equals 123.456(789). Is there an efficient algorithm to determine the lengths of the fractional parts or one that does at least provides reasonably tight bounds on them? I did quite a bit of research at the time but only with limited success. I am reasonably sure that finding the exact lengths is comparable in hardness to factoring p and q in some cases and possibly harder in the general case. But I did not come across much with regard to bounds on the lengths. Maybe there was somewhere an implicit answer to my question which I did not recognize or fully appreciate due to my limited knowledge of number theory but I never came across an explicit statement that said that printing the decimal representation of a rational number or estimating its length is a hard or unsolved problem. I ended up just performing the expansion digit by digit until I detected a cycle or reached a specified maximum length, but it would by nice to know in advance how long it will be or at least to learn that this is actually an hard or unsolved problem.
- tadkar 9y agoWhile I’m sure you know this, when computing the fractional part you will have at most q-1 digits in your repeating cycle. When you divide by q, you have at most q unique remainders (0 to q-1). Also when computing the fractional part, if you end up with the same remainder as you’ve previously seen then you’ve hit the cycle.
- danbruc 9y agoThat is exactly what I did, I implemented some cycle finding algorithm, a tortoise and hare variant maybe but I can not tell from the top of my head, on the reminder sequence giving up after a user-specified number of steps. But it irks me that this may abort just a hand full of steps before finally finding the cycle. And unfortunately q is just way to loose as a bound if it even deserves the name bound in this case. I initially started looking into this because I wanted to print something like »0.577 215 664 <901,532 more digits>« but in that case q is essentially useless because you either have to really search the cycle which quickly becomes impractical once q reaches millions or billions or you have to live with »0.577 215 664 <up to 999,999,991 more digits but maybe also just one>«.
- SloopJon 9y agoFor Mac users trying this at home, I made the following changes to build and run the tinypi tests on Sierra: 1. Comment out the malloc.h include in tinypi.c. 2. Add -Wno-unused-function to CFLAGS. 3. Use shasum, rather than sha1sum, in the test target.
- wnoise 9y agoHaving malloc.h as an include is bizarre, anyway. The standard location for malloc and related functions is stdlib.h, and removing that include should let it still compile on any reasonable platform.
- cryptonector 9y agoThis is perfect for jq[0]. [0] https://github.com/stedolan/jq https://github.com/stedolan/jq
- guipsp 9y ago...How is it perfect for jq?
- cryptonector 9y agoIt has a suitable license (MIT), is rather complete, and has semantics that will not surprise jq users.
- jwilk 9y agoWhy does jq need arbitrary precision floating-point numbers?
- cryptonector 9y agoThe most FAQ / most filed issue for jq may well be that IEEE754 sucks. Users are frequently surprised by IEEE754 issues.
- dnautics 9y agonot that it's needed, but JSONschema has this kind of crazy part where it lets you do multipleOf for floating point numbers. Of course 2.7 is not a multiple of 0.3 in IEEE-64-bit FP.
- geofft 9y agoBecause JSON's spec defines a "number" as an arbitrary-precision floating point number, no limit on how many digits can be before or after the decimal or on what positive or negative integers you can put after the "e". Despite the name "JavaScript Object Notation," it does not inherit JavaScript's traditional interpretation that a "number" is an IEEE 754 double. (JSON also does not permit infinities or NaN, which JavaScript does permit.) http://json.org/ http://json.org/
- abetusk 9y agoFor those that don't know, Fabrice Bellard is the author of ffmpeg [1], the tiny c compiler (tcc) [2], linux in the browser [3] among many others [4]. Does anyone know how LibBF stacks up against GMP? [5] [1] http://ffmpeg.org/ http://ffmpeg.org/ [2] https://bellard.org/tcc/ https://bellard.org/tcc/ [3] https://bellard.org/jslinux/ https://bellard.org/jslinux/ [4] https://bellard.org/ https://bellard.org/ [5] https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithme...
- nuclx 9y ago[6] https://www.qemu.org/ https://www.qemu.org/
- tzs 9y ago> The basic arithmetic operations (addition, subtraction, multiplication, division, square root) have a near linear running time I thought the best known multiplication algorithms (the ones based on Fourier transforms) for large numbers are a little slower than O(N log(N)). Has something better been found?
- dbaupp 9y ago"near linear" is sometimes used to refer to O(n log(n)^O(1)), that is, things that are linear other than a polynomial of log(n). This includes Schönhage–Strassen multiplication, with its O(n log(n) log(log(n))) complexity.
- kuwze 9y agoThere is also BSDNT[0] (which is obviously BSD licensed) in case anyone is still interested... I think this takes the cake though (as it is MIT licensed and superior). [0]: https://github.com/wbhart/bsdnt https://github.com/wbhart/bsdnt
- kuwze 9y agoI also just realized that this is only for big numbers, not arbitrary precision.
- rurban 9y agoThis needs some major work to be packagable into a library, esp. for non amd64 hosts. There's also no src repo, as with all his previous hacks. Who will do the autotooling and repo hosting? I've added some sugar in my fork on github https://github.com/rurban/libbf/tree/my https://github.com/rurban/libbf/tree/my but I'm not sure yet if I will use it. But the low constant overhead for small numbers, the small size, no assembler tricks and the MIT license makes it very attractive.
- rurban 9y agoI think the name is also already taken, for brainfuck and bloom filter.
- peatmoss 9y agoPerhaps a side digression to this conversation, but... in spite of all the cool languages we talk about that have many on-paper advantages of either safety, convenience, or support of paradigms, is there really any option besides C for this kind of thing? It still seems that, if you want to write Core Infrastructual Code that can be run anywhere, on anything, that links with any other software without any caveats, disclaimers, or compromise, C is still king. Could this have practically been written in rust? haskell? ...and still have the same degree of embeddability and reach?
- isaachier 9y agoIn my limited experience, no. All of the languages you mention put developer experience above portability, so usually require a basic runtime. C on the other hand is not interested in saving you from the machine, which allows for extremely minimal programs. Even C++ isn't great here compared to C. Then again, debugging segfaults isn't for everyone, so most are fine giving up C.
- whyever 9y ago> All of the languages you mention put developer experience above portability, so usually require a basic runtime. Rust's runtime is comparable to C's. It is less portable because it uses LLVM as a backend, not because of the runtime. > Then again, debugging segfaults isn't for everyone, so most are fine giving up C. Depending on the application, having vulnerabilities due to undefined behavior is a much bigger problem than having to debug segfaults.
- nomonomus 9y agothen port it to gcc?
- steveklabnik 9y agoWe’d love to see a gcc front end for Rust. Someone attempted one in the pre-1.0 days, which was... not simple. Someone has to step up and do it though.