[Toybox] Toybox bc's transcendental and irrational functions produce incorrect results, memory leaks and exhibit brute force algorithmic complexity.

[Rob Landley]

On 08/28/2018 12:35 AM, Sasha Toltec wrote:
> Wait.. what?

Commands in pending/ default to "n" in defconfig. Some of them are nearly
finished and just need more review, some are stubs that don't do anything
useful, and some need complete rewrites.

This is normal for toybox.

> Am I really reading an email signed by two people?

People keep emailing me about drama behind the scenes in this command's
development, interchanging handles and names of people I barely know and can't
really track. I'm trying to stay out of it, but don't personally have the domain
expertise to write this command myself, nor the 3-ish months to come up to speed
in this area enough to use existing algorithms explained on wikipedia and similar.

I'm told the main source of drama is somebody named "Graff" who got banned from
#musl, and Rich is _way_ better at dealing with people than I am. I've been
tempted to reject the bc implementation just because it's not worth the drama
(and already deleted an earlier version from pending rather than wait for an
update as I usually do) but if it's just one troll sock puppeting that's nobody
else's fault.

> First off, you used subtractive chunking for division. Calling this a
> naive algorithm is giving it more credit than it is worth. The only
> time subtractive chunking is used is by school children.

And drama. How nice.

Have you seen my factor implementation? It's naive. The largest 64 bit prime
number is 2^64-59, and ubuntu's factor returns that it's prime basically
instantly (even on my tiny little 5 year old $200-when-it-was-new netbook), but
my version:

$ time ./factor 18446744073709551557
^C

I got tired of waiting after about 3 minutes.

My code, which I authored, sucks. I knew that when I checked it in. Patches
welcome. (That said, the 80/20 rule applies: small and simple and works for the
common case, then wait for people to show up with personal use cases in the
remaining 20%...)

> I cloned your repository (van Rijn and Howard?)

van Rijn is the guy who hosts the musl-cross-make toolchain binaries at
http://b.zv.io/mcm/bin/ and he's Thalheim on the IRC channel. He's always been
polite and has a history of helping out. I trust his judgement.

(According to Girl Genius he created the nine muses, but his other projects are
his business.)

> https://github.com/gavinhoward/bc/
> 
> You (both?) seem to have no idea how to force errors out of a badly
> scaled irrational function

I don't either, for the record.

> so I supplied an example (though judging
> from the first example I gave, you (both?) will just lie/boast and say
> this one works on your system too!):
> 
> echo "sqrt(.0000000000000000000000000000123)" | ./bc -l
> .0000000000000035071539807692832
> echo "sqrt(.0000000000000000000000000000123)" | bc -l
> .0000000000000035071355833500363
> 
> As you can see, the "solution" is not even close.

Nineteen digits of precision is not even close?

What I usually do is add failing test suite entries to remind me of issues I
need to fix. Happy to merge patches against tests/bc.test. Let's see... Huh.

  landley at driftwood:~/toybox/toy3$ TEST_HOST=1 time make test_bc
  ...
  598.95vuser 257.87vsystem 14:14.24velapsed

The _host_ version takes almost 12 minutes to run this test. Most of which is
spent in "generating", and spits out a couple "(standard_in) 1: syntax error"
lines. That should probably be fixed somehow (running "make tests" to test
_everything_ should be a feasible thing to do on a regularish basis, this one
test can't take this long, maybe it should have a "short" version or
something... Another item for the todo heap.)

Anyway, adding _this_ test looks like... commit e579e69656b3

> It is very hard to produce test results from such a badly made
> library, as it has actually taken my computer offline twice now (by
> overusing memory and other strange bugs), but I will give it another
> go:

Historically, this bc implementation has had one troll, who sock puppets.

> This command takes 25 seconds using your math (if you want to call it
> that), but only .01 seconds using a correct implementation:

I'm ok with that. Patches welcome, but that's not a blocker for me.

> It is easy to scale this to take more time than the lifetime of the
> universe while other implementations are still instantaneous.

See "factor", above. Which I wrote on a long bus ride while reading
https://www.muppetlabs.com/~breadbox/txt/rsa.html which used "factor", and I
went "that looks easy enough"...

> I revved your repository back using git checkout and discovered a
> sordid history.

A) One troll, with a history of sock puppetry.

B) Toybox just checked the results into pending. If toybox's maintainer doesn't
care about the history before that (other than confirming it's under the right
license, and the fun bonus that people who know about it are hanging around to
do more work on it as necessary), why would you?

> Including an entire fast arbitrary precision
> implementation written by other authors (appears to be CM Graff and
> Bao Hexing) which was stripped, renamed and then badly reimplemented.

Hello Graff. You can stop now, you've been made.

> Please just fix your fix your "implementation" (if one can really call
> it that) and stop wasting everyone's time.
>
> Sasha Toltec
> Toltec Enterprises
> sashatoltec1 at gmail.com

Who does not exist according to Google.

Do I need to switch on list moderation for new subscribers?

Rob