How to init an array in Posix bc?

[ewmayer]

Originally Posted by paulunderwood

Without -l, just bc -q ...

bits(2^100)
102
bits(2^101)
102
bits(2^102)
102

You still need to home in from a ballpark figure. Right?

Yes, of course, since counting dec-digits leaves lots of wiggle room re. #bits ... shoulda tested my brilliant idea on a few more data than the trial number I used, for which the dumb 1-line formula happens to produce the correct result.

The revised function, assuming no mathlib loaded or mathlib loaded and scale=0:

define fast_count_bits(n) {
        auto r;
        r = length(n)*3321928095/1000000000;
        while ( 2^r > n ) { r -= 1; }
        return(r+1)
}

Yep, but farewell 'virtual instaneity', we hardly knew ye. :(

But hey, what is trial without its necessary-for-learning partner, error?

[paulunderwood]

Computing 2^r is the slow thing and that could be done 3 times. Given such a worst case, how does it compare with your recursive divide and conquer function?

[ewmayer]

Originally Posted by paulunderwood

Computing 2^r is the slow thing and that could be done 3 times. Given such a worst case, how does it compare with your recursive divide and conquer function?

I tried 2 different divide-and-conquer algos - one based on division, the other on multiplication, both by power-of-2 powers-of-2. Thus both also need to compute multiple - O(log2(bits(n)) - powers of 2 ... the multiply-based on was ~10x faster on a 500-kbit input than the divide one because MUL is faster than DIV. The latest, length()-based version runs indistinguishably different in terms of time than your mathlib-log-based version, i.e. both are slightly faster than faster (multiply-based) one of my divide-and-conquer algos.

Having btiwise functions bits() and reverse() allowed me to compare RL and LR binary powering algos ... the latter runs in ~60% the time of the former for a typical scenario: for a base-3 PRP test of the ~thousand-decimal-digit m-prime M3217, RL needs ~60 sec, LR needs ~30 (this is best-case for LR because nearly every exponent bit = 1; for quasirandom exponents LR typically needs 2/3 r=the runtime of RL).

Basic gcd and egcd also work. May play with extended factoring functionality (p-1, later ecm and possibly qs) next, but first a deeper look at the NT-for-bc link you provided over the weekend.

[xilman]

How many systems around here do not have Perl installed? AFAIK it runs on almost everything and is an essential part of the system for anything which is even vaguely Unix-like.

Ernst: if you have Perl just use it. It's so much more flexible than bc.

[paulunderwood]

Originally Posted by xilman

How many systems around here do not have Perl installed? AFAIK it runs on almost everything and is an essential part of the system for anything which is even vaguely Unix-like.

Ernst: if you have Perl just use it. It's so much more flexible than bc.

I advocate Ruby. It has a decent interactive shell. It supports arbitrary precision out of the box. It has a rich set of functions. However, I found some bugs in Bignum (now Integer) in earlier versions than 2.1

[ewmayer]

Paul, of course Perl is much better suited for such stuff, but permit me my little exercise in getting-a-really-dumb-dog-to-perform-some-new-tricks-ery - it's a nice bit of fun for times when I need a break from my usual serious coding work but still wish to keep my brain in code/algo-focused mode.

By way of somewhat-answering the question I posed in the OP, bc's limited programming functionality forces one to resort to kludgery in order to support any kind of reasonable const-array-init, but it's not too bad for some common kinds of inits. For example, in my C codebase I have a utility function to generate a table of all odd primes up to some bound, whocse current limit is 2^32. Said function uses a simple mod-3,5 sieve and feeds the resulting candidates to a Fermat 2-PRP routine. That needs an auxiliary table of known Fermat base-2 pseudoprimes, of which there are 9366 < 2^32 not divisible by 3 or 5. So let's say we want to code similar in bc, restricting ourselves to prime < 10^8. We can do this by taking our C-code array-init for the Fermat base-2 pseudoprimes, excerpting the entries < 10^8, reverse-sorting them, left-0-padding all entries to 8 decimal digits, concatenating the results them into a long decimal string, and feeding same to a loop which does repeated mod-and-div-by-10^8 to init our array. The yuuge decimal string is not particularly fuglier than the big comma-separated table used in the C-code's array init, and the repeated-div loop needs just a few seconds to run. The associated small-primes-init code needed ~60 sec on my Core2 macbook to generate the first 65536 odd primes, which is of course really slow, but not egregious to support such basic-foundation operations in bc. Code attached.

[chris2be8]

Another reason for avoiding bc is that it's a lot slower than GMP. I've just updated my script searching for algebraic factors of number in factordb to work out what the number evaluates to with pexpr (sample program shipped with GMP) instead of bc and it's dramatically faster.

time pexpr '(74^16820-1)/1791051738450034974183457153894994534200971751588579164486402699442174091407878519893290614801' >/dev/null

real    0m0.017s
user    0m0.012s
sys     0m0.004s

echo '(74^16820-1)/1791051738450034974183457153894994534200971751588579164486402699442174091407878519893290614801' | time -p bc >/dev/null
real 0.17
user 0.16
sys 0.00

So pexpr is more than 10 times faster. Which makes quite a difference when I'm doing it several times a second. And some of the numbers I'm processing are a good bit larger than that example.

Chris

[ewmayer]

I would never recommend bc based on speed, but it has the advantage that you don't need to download/install it. I.e. if I want to play around with some not-huge bignum calculations on any of my posix boxes, "it's just there". I've had numerous build/install fails with gmp under various versions of macos in the past, an issue that is quite common if you're an OS-upgrade-Luddite like me, who likes his macOS 10.6.8 because it was the last version of said OS before Apple succumbed to featuritis and turned its subseqent versions into iOS-driven bloatware. (I have a backup macbook running 10.7.5 and the few times I've used it I've wante to tear my hair out, it's so bloody ^!%&$ slow).