IQ4sh - Calculator for CLI or scripts -Testers wanted

[misko_2083]

A while ago I've used one written in pure bash https://github.com/bluebat/.bash/blob/master/bashbc.sh

Code: Select all

bashbc.sh 2.555+6.335
8.89
scale=2 bashbc.sh 2*(3/7)
0.84

Not so precise when it comes to rounding 0.857142857143, but was good enough for a progressbar.

[MochiMoppel]

@MochiMoppel Interesting that iq is outperforming bc there

that was the purpose of your project, wasn't it?
As I said iq becomes slower than bc when total digits exceed 16. Using 18 digits as in mul 123456789 123456789 would typically return

Code: Select all

--- bc -------------------
15241578750190521
real	0m0.007s
--- mul ------------------
15241578750190521.0
real	0m0.072s

However when fractions come into play as in mul 12.3456789 1234567.89 , the same 18 digit multiplication mysteriously becomes faster Observed over a couple of iterations, so it's not a one-time wonder:

Code: Select all

--- bc -------------------
15241578.750190521
real	0m0.010s
--- mul ------------------
15241578.750190521
real	0m0.005s

one-shot and head-to-head -is that with bash and busybox bc, or...?

when sourced in bash sh, tested against full version bc (my busybox comes with a crippled dc, no bc). I didn't test in ash as the time command in ash doesn't support functions.

All the shells in question have a 19-digit maximum for inputs and outputs. No single number can be longer, and the output can be max 19 digits.

Yes, that's the maximum but only for certain values. 18 digits is safe regardless of value.

Code: Select all

# echo $((1999999999999999999)) # 19 digits
1999999999999999999
# echo $((9999999999999999999)) # 19 digits
-8446744073709551617
# echo $((999999999999999999))  # 18 digits
999999999999999999

[amigo]

Total digits in output can't exceed 19:

Code: Select all

echo $((999999999999999999 * 99))

@misko_2083 That bashbc is quite a find -but it is certainly full of bashisms. Maybe it works under zsh/ksh -I'll be looking at it for goodies, for sure. I don't immediately see how it works - a quick test shows it is slow, and only seems to work for a small range of values/scales. I'm out for the day, but I'll be looking at it anyway. Thanks for the tip.

[amigo]

Okay, I just pushed the fix, in iq, for mul and another fix for div -we are approaching the last that matter. There are also changes in iq+. I found a really great Pade approximation(thanks Zeda Thomas), which is small, fast and super accurate. It completely replaces the former implementation.

@misko_2083 That bashbc is really crazy because it doesn't use expr or $(()) at all. But it's useless for my purposes -scale seems to be limited to 5 and it only handles a small range of numbers/lengths. I'm surprised I never found that, as many times as I searched for 'bash calculator'. And about the Vedic methods, they require many special treatments -like according to the last digit, etc. I think I did use some Vedic concept in my binary calculator 'bin4sh'. Have you tried iq/iq+?

[amigo]

All fixed now, with other minor things I found.
About the single-dot with mul - '.' is used as a multiplication operator in some circles/countries, so for mul it is considered a valid operator. Perhaps I will change that so that it is more consistent with elsewhere. bc handles that the same way as with 'blabla' -it sees no valid number, so it assumes it is zero.

About input validation in general: It would take a large number of checks to figure out if any input is completely valid, whether it's a value or, especially, if it's an operator.
For values:
check if it contains any non-numeric chars(like isnum does)
then check if it has both '+' and '-'
check if it has more than one +, '-', or '.'
check if it is a single '.'
check if it has any trailing '+', '-', or '.'
These could all be checked with one function -along with possibly other checks.
But, checking the operators would require separate checks, depending on which operation is being called.
And this is further complicated because operators are not required for mul and are optional for add. add is even more complex, because we accept to types of notation, with or without operator, for each iteration. You can do:
add 2 -3, add 2 - 3, or add 2 + -3
Even mixed:
add 2 -3 2 - 3 2 + -3
When there is an operator, we have to do a second evaluation of the signs, so x + -y and x - -y get handled correctly.

Here are some timings for comparison:

Code: Select all

time ./iq+_1.68.sh exp -s12 0.835
2.304814048287
with bash:
real    0m0.188s
user    0m0.144s
sys     0m0.051s

with zsh:
real    0m0.148s
user    0m0.128s
sys     0m0.025s

with posh:
real    0m0.156s
user    0m0.112s
sys     0m0.047s

with dash:
real    0m0.077s
user    0m0.067s
sys     0m0.010s

with ksh:
real    0m0.037s
user    0m0.031s
sys     0m0.004s

About comparing with bc/awk and my purposes, I didn't really set out to compete with, only to replace them -as a proof-of-concept. It was obvious before starting that speed would always be a problem -even as an experiment. It was only recently that I tried a complex problem comparing iq+/bc/awk, that I saw iq reaching close, speed-wise, to bc/awk. Meanwhile, iq+ was already doing things that neither bc or awk do, like the exp function and, for bc, even exponentiation. In timing bc, you'll see that any valid construct takes about the same time to run, no matter what scale you use(or input length). However iq will always take longer the longer the inputs. That's why all the anguish over anything that slows it down -particularly in add and mul, as they may get called hundreds of times for an nroot/pow problem. And for a really long divide, the whole thing will be done with subtraction.

Neither awk nor bc have factorial, nroot, pow or other functions which iq/iq+ already include. That iq can compete or compare ~anywhere~ is surprising. That it can even go beyond, even more so.
Thanks again for feedback.

[MochiMoppel]

# mul - fixed multiplication of/by 0 with early exit -thanks MochiMoppel

Your're welcome. Unfortunately not fixed.

Your code in question:

Code: Select all

        # if either number was 0(null by this point) or 1, exit early.
        case $Bm in ''|0) echo 0$defzero ; return ;; esac
        case $Am in ''|0) echo 0$defzero ; return ;; esac

Example $1=0 and $2=123456789012345
results in $Bm=123456789012345 and $Am=<empty> , so case matches and function returns 0. That's good.

Now increase value $2 to 16 digits:
$1=0 and $2=1234567890123456
results in $Bm=00 and $Am=12345678901234560 , case does not match, i.e case doesn't work for larger numbers

You probably could fix this by changing case condition to ''|00 or ''|0|00 but there still remains a weak point: If you have more than two, potentially large factors and only the last is zero you would still have to go through lengthy multiplications before you reach your "early exit" point. I have a better idea (I hope): let the very first line in mul be something like

Code: Select all

case $@ in [.0]\ *|*\ [.0]\ *|*\ [.0]) echo 0 && return ;esac

Checks for 0 and (zero substitute) single point and can of course be extended to include more odd values like 0.0 or .0.
Time here is "real 0m0.001s" - beats any bc calculation hands down

[amigo]

More concerning than this:

Code: Select all

time ./iq+_1.69.sh mul 127357181233333333333332678  .1 0.0000000001 0
0.0
real    0m0.024s

time echo "( 127357181233333333333332678 * .1 * 0.0000000001 * 0 )" |bc
0
real    0m0.004s

is this:

Code: Select all

time ./iq+_1.69.sh mul 127357181233333333333332678  .1 0.0000000001  
1273571812333333.33333332678
real    0m0.026s

time echo "( 127357181233333333333332678 * .1 * 0.0000000001 )" |bc
1273571812333333.3333333267
real    0m0.004s

See the last digit missing from bc? I'd rather the lose the first contest and win the second -which we do here.

Anyway, I played with your examples for a while to see what might be improved. What can I say, we could chase after special cases for ever. At some point GI must reduce to GO. The leading lines of the main functions have been refined over a long time. If you look closely, you'll see that all the padding and depadding have to be handle slightly differently for add, mul and div. And for each of them, the pad/depad routine usually varies, depending on whether the problem is handle one-shot(natively) or as a long -possibly very long, problem. The same holds true for handling the operators -especially since they are optional in some cases. For mul, the operator is completely unused. Rejecting a single dot as invalid, treating it as zero or whatever costs some checks. For add, a zero in the middle of a series doesn't require an exit with answer 0, so it can simply be handled normally.

Your suggested check for any zero value in all inputs at the top would still require deconstructing some inputs completely -you can't write enough special cases to differentiate possible errors. In general, any check anywhere for a special case is a bad idea, when your normal method of processing will catch it. Checking for a real zero value is harder than it looks -even when it IS zero. Your suggestion wold burden every call of mul needlessly -if the check turns out okay, you still have to de-construct, normalize, examine and re-construct each input. Of course, the values 0 and 1 are special cases, depending on the operation. For add, zeros won't change the result, but 1's will. For mul, we CAN handle zero early, because it WILL change the result to a known value and an exit condition. Since add and mul work on a series of numbers, the fastest method is to handle the inputs one at a time -with a general method. That's why we can check for null, 0 or 00 -because all the crazy inputs like 0000000000.000000000 are already uniformly sanitized -by de-padding and padding. But, what works for one function will not work for all of them.

While paying attention to your suggestions, I've implemented a new 'exp', which I've used to rework 'pow' with better range and much faster:

Code: Select all

time ./iq+_1.69.sh pow -s7 1.357 12.645  
47.4757870
real    0m4.767s

time ./iq+_1.69.sh pow4 -s7 1.357 12.645
47.4757870
real    0m0.456s

See those 4,300 milliseconds (10+X) difference? That's where I need to be tinkering -even more so because it also eliminates the call to nroot&Co. I have changed a couple of lines in mul to reduce: case ''|0|00)... to simply case '')... -by -you guessed it, depadding both numbers the same way, so that the 0 and 00 cases are always eliminated. This also means that more inputs will fit into the short operation. It's worth noting that, the mul chunking routine does need any depadding, front or back, to work. Unlike add, where the decimal points of two inputs have to be aligned, mul is able to work unaligned, even on variable-size chunks. But depadding speeds things up.

Maybe I will be ready to push a while later -for your enjoyment with breakfast...

[MochiMoppel]

More concerning than this <snip> is this <snip>
See the last digit missing from bc?

I see, and I'm not concerned. I never use bc this way for multiplication.
For obscure reasons bc sometimes skips trailing digits. Always adding a (huge) scale can fix this. I also use to set BC_LINE_LENGTH=0 to keep bc from breaking long output lines (try to multiply pi with 1000 digit precision ...).

Code: Select all

# echo "2.001*0.004" | bc                               
.008

# echo "scale=999999 ; 2.001*0.004" | BC_LINE_LENGTH=0 bc                       
.008004

[6502coder]

I know this is somewhat off-topic, but out of genuine curiosity...who needs so many significant digits in their work? Number theorists, obviously, and historically astronomers needed mind-boggling precision, but who else?

One of the first lessons I learned when I studied numerical methods was that if you are working with lots of significant digits, you have probably mis-formulated your problem. Often it is just the tiny DELTA between two humongously long quantities that you are really interested in, and so if you recast the computation to be in terms of the delta, you don't need all those significant digits. Not always, but often.

[amigo]

@6502coder Since shell math is integer-only, the techniques are kind of like bignum. We reduce as much as possible to text-processing , which is also bignum-ish. I didn't really intend to make an arbitrary-scale calculator, But I certainly wanted to be able to work with numbers long enough to calculate a sigmoid, powers, roots and other stuff. Of course I needed the basic maths to work very well -and later faster. It was all just a proof-of-concept -being able to demonstrate a learning neural network -entirely with shell script.
The chunking method I developed naturally allowed the numbers to be as long as a shell variable can be -which is >16sextillion -yes, digits.
As it turned out, some guys on another forum tried to confirm a answer that iq+'s epow function was returning. They tried python, perl, awk and Galculate, IIRC. They tried several different bignum libraries for perl/python before finding one which would come close, and another succeed. I hade been using the fine casio/keisan online calculator for quick answers to things like this:

Code: Select all

time iq+ epow -e20 0.014 ^ 100
4.10018608884993288052e-186
real    0m0.148s
 

But, I had pumped up to 0.014^10million, when casio gave up, so ask around for verification. some of the awk/perl/py coule answer that trivial problem. Meanwhile, I had tried stuff like ^10trillion, and showing consistent answers all the way.

Code: Select all

time ./iq+_1.69.sh epow -e20 0.014 1000000000000000
1.06151455931166568355e-1853850000000001
real    0m2.384s
or, faster
time iq+ epow -e7 0.014 1000000000000000
1.0615145e-1853850000000001
real    0m1.216s

The -e7 means use 7 SigFigs(plus a couple) for the calculations. Even that last problem takes less than 30 iterations -using a squaring-halving routine with a twist that might interest you, sounds like. And epow would actually print that out as a non 'e' notation if you want in truncated scale or SigFigs after all those leading zeros. Or, you can do this:

Code: Select all

time ./iq+_1.69.sh epow -e70 0.014 10000000
2.2739576923951688855681020876547705104590590157730952690274434712171790e-18538501
real    0m3.856s

Thanks for chiming in 6502 -unfortunately I was out most of the day and couldn't push the latest changes -I'm still doing some sanity/security bits. Interested to know if you can flush out any errors, assuming sane inputs.

[6502coder]

@amigo

I am intrigued by numerical methods so I did have a quick look at your work. It's really amazing stuff. I only wish I had a better grasp of what's going on, so that I'd have a better idea of what would make good test cases, excluding nonsense inputs.

[misko_2083]

Okay, I just pushed the fix, in iq, for mul and another fix for div -we are approaching the last that matter. There are also changes in iq+. I found a really great Pade approximation(thanks Zeda Thomas), which is small, fast and super accurate. It completely replaces the former implementation.

@misko_2083 That bashbc is really crazy because it doesn't use expr or $(()) at all. But it's useless for my purposes -scale seems to be limited to 5 and it only handles a small range of numbers/lengths. I'm surprised I never found that, as many times as I searched for 'bash calculator'. And about the Vedic methods, they require many special treatments -like according to the last digit, etc. I think I did use some Vedic concept in my binary calculator 'bin4sh'. Have you tried iq/iq+?

There are few on github and gitlab https://github.com/search?q=bash+calculator
https://github.com/Phate6660/bcalc/blob/master/bcalc
$(()) is very handy.
The good thing about it can do several expressions in one line, separated by comma.

Code: Select all

echo $(( n=20, n=n+30 ))

There is also "? :" which can be used as an alternative to if statement

Code: Select all

n=20
var1=10
var2=0
echo $(( n>=20 ? var1 : var2 ))

Condition ? true : false
If the condition returns true then it will execute the statement that is defined before ‘:’ otherwise it will execute the statement that is defined after ‘:’

[amigo]

Thanks 6502 and misko. I wasn't really aware of: $(( n=20, n=n+30 )). I have seen $(( n>=20 ? var1 : var2 )), before and it works under all my target shells: bash, zsh, posh, dash and ksh. $(( n=20, n=n+30 )) works under all except dash, which means we can't use it.

About the github projects, bcalc is purely bashisms, so is out. azzen/calc is just a front-end to bc, shellmath.sh is all bashisms, bash_calculator sh is short, integer-only, and so on. I see that bcalc was started after I began - I've been working on this for 2 years with re-writes.

I really hope to push new changes today -I'm working on anti-code-injection stuff to avoid idiots doing things like this:

Code: Select all

iq /bin/ls
iq add 1 + evil-command
 

I'm also hoping to eliminate any places where iq tries to give an answer, where there is none -but within reason. Mostly, anything that will produce an error from the math unit, is not checked for. I'm trying to achieve a balance between thoroughness and speed -with speed being the priority. Wherever garbage-in poses no danger, I tend to stick to speed. The basic functions usually have some sort of early check for easy answers. Since I don't check for alpha-characters in inputs, doing something like this produces funny output:

Code: Select all

iq div bla / bla
1.0
iq div bla / 1
bla

Logically, those are actually correct answers!

Code: Select all

iq div bla / blad
./iq+_1.69.sh: 82: [: Illegal number: +1bla00
./iq+_1.69.sh: 83: [: Illegal number: +1bla00
./iq+_1.69.sh: 82: [: Illegal number: +10bla0
./iq+_1.69.sh: 83: [: Illegal number: +10bla0
./iq+_1.69.sh: 434: [: Illegal number: bla00
./iq+_1.69.sh: 437: arithmetic expression: division by zero: " bla00 / blad "
2

If I leave out the early-exit clauses, the first two examples get an answer like the last example. As I've stated before, I'm not gonna explicitly check for every possible sort of garbage inputs -even if they produce some sort of funny answer. The number of sanity checks is already higher than needed -if we assume proper input. We still have to sometimes check for _appropriate_ inputs for the pow/logx/nroot functions.

I'll post later when I've pushed changes to github.

[misko_2083]

Testing now. Good work on the script.
One thing I noticed is it doesn't do rounding.

Code: Select all

./iq add  3.47451 + -3.5555
-0.08099
./iq add -s3 3.47451 + -3.5555
-0.080

But can always do this:

Code: Select all

round() {
    printf "%.${2:-0}f" "$1"
}
round $(./iq add  3.47451 + -3.5555) 3
-0.081
round $(./iq add  3.47451 + -3.5555) 4
-0.0810

[amigo]

Guys, I've just pushed changes from the last 3-4 days, so update your copy. About rounding, I used to do that, as well as fancy output padding (think dollar format), but it gets too complex and slow. Questions about the correct way to round, in X situation, etc., make it all too much for my needs. I used to use printf where it was handy, but it fails for really long numbers, and for other reasons it's gone.

In the old days, 7 Puppians would have pounced on the project from start to make a gtkdialog front-end. A more user-friendly and usage-strict frontend is a better place to tackle such stuff, rather than burden the underlying functions more -there is NO end to the crazy inputs one might encounter, since iq ca'nt disable all your keyboard except for the num/op keys.

A fellow on LQ has already been creating rpm packages of iq/iq+. I've promised to start working on the man-pages and I'll have a few extra files to upload, like BUGS, AUTHORS or STYLE.lack-thereof to push. The help functions and comments, everywhere, are still being polished, improved. Let me know what I'm not being clear about, and any incorrect answers you find.

Thanks to all of you!

[amigo]

Sorry, had to fix a regression after applying a (wrong)fix suggested by shellcheck. I'm hoping for a new year without regressions...
If you pullled after last post, pull again.

[MochiMoppel]

While paying attention to your suggestions, I've implemented a new 'exp', which I've used to rework 'pow' with better range and much faster:

Code: Select all

time ./iq+_1.69.sh pow -s7 1.357 12.645  
47.4757870
real    0m4.767s

time ./iq+_1.69.sh pow4 -s7 1.357 12.645
47.4757870
real    0m0.456s

See those 4,300 milliseconds (10+X) difference? That's where I need to be tinkering -even more so because it also eliminates the call to nroot&Co.

That's very impressive indeed and I copied iq+ version 1.70 hoping to find pow4. Is it still to come? I checked pow and it seems to be the older version, still calling nroot though overall a tiny bit faster than previous versions.

Anyway, I envy you for your fast computer. Want to see my time with my 12 years old Atom Netbook? Don't be shocked:

Code: Select all

# time iq+ pow -s7 1.357 12.645 #unmodified iq/iq+ v.1.70 
47.4757870
real	0m46.866s

I managed to reduce this time by around 10% when changing only one line in iq+

Code: Select all

# time iq+ pow -s7 1.357 12.645 #modified fpow
47.4757870
real	0m41.860s

If you are interested I can explain but I can also understand if you want to bring your project to an end and stop all your tinkering.

As you know I started a bit of tinkering on my own and tried to write a mul function from scratch, imitating a "by hand" multiplication, multiplying each digit of factor a with factor b. I expected that processing times for my simple mmul would be considerably slower than your sophisticated mul , but now all indications are that mmul can be much faster than mul, depending on digit length, For small numbers both are about equal and outperform bc when used as sourced functions, but speedup for larger numbers can reach 10X , on average it's about 5X ~ 6X.

mmul is still a bit untidy and needs polishing but it's functional. For fun and out of curiosity I replaced your mul in iq with mmul (renamed it of course) and tried your example again, first with an unmodified iq+:

Code: Select all

# time iq+ pow -s7 1.357 12.645 #mmul
47.4757870
real	0m9.297s

pow is very complex and I have no clue what's going on there but this boost in speed suggests that pow's performance depends largely on mul's performance.

After modifying iq+ (which reduces the number of calls to mul from a whopping 535 to 408) processing time decreases further:

Code: Select all

# time iq+ pow -s7 1.357 12.645 #mmul ;modified fpow
47.4757870
real	0m8.703s

I more or less achieved my goal, and so apparently did you. Finally something good comes out of 2021. Happy New Year!

[amigo]

@MM, thanks very much for everything. Yes pow4 is still to come -it uses an a^x = e^(various possible ways). The original pow does a real calculation of the answer to a^x, but by using any variation exp (e^?) we can use an approximation. We've had an exp for awhile -a Taylor and a MacLaurin series where accuracy was limited to ~11 places. And achieving X-places accuracy requires more and more iterations. That version of exp was replaced last week with a really brilliant Pade approximant which I have already achieved 80+ places for VERY small input values. Using that in pow4, but only for exponents with fractions -but this way we don't need nroot anymore . But the old and new exp only work in a limited range -and reducing large inputs into that range takes time and and may reduce accuracy.

'finish' is hard to define. Yes I do want to get 'there', but I want it to be right and so that nothing needs to be added, nor removed. We are a shell-script so speed is always priority #1 -but we need to have a bit of flexibility for the users with an eye to understandable syntax. We were doing badly at handling mal-formed inputs -simply because I was writing for best speed when used in scripting. At first he whole user-interface was just a way to quickly check results while developing. I'm not complaining about having a UI -it is key to finding users anyway. And, since iq has really become very capable and even faster or more complete than other CLI calculators(sometimes), it is more widely useful.

I'll certainly look at your modified functions. I think it best to not clog this thread with code other than 2-3 line snippets, maybe attach them here or email me. Substituting a couple of lines in an existing function is a good way to try small changes out. Or, write a complete replacement function and switch names with the original function to test. But creating a none-to-one replacements is take LOTS of testing -and make sure it can handle 10,000+ digits -I tested 'div' to that length once.

@MochiMoppel @6502coder -fpow is the raw exponentiation method used everywhere. It uses the squaring/halving method. I also tried using mod with it for very long numbers, bit was slower. 6502, epow uses the same method with a twist -all inputs are turned into decimal. Using log, we can calculate the size of the result integer, make the input a fraction -from log we also derive how many leading zeros will be in the result fraction. This means we can _know_ how precision we need for each intermediate multiplication -which is the supreme problem with exponentiation(ipow takes much longer to calculate for precision than for ops). Then, for each iteration of squaring/halving, in epow, we remove any leading zeros in the always-fractional intermediate product. That means that we don't need to increase precision after an initial calculation with a bit extra to eliminate short rounding errors.

My original fpow was adapted from ruby, I think. But that trick with epow is my own 'invention' -if it's already out there I didn't find it. The one example of 0.024^10,000,000,000,000?? only takes about 30 iterations, at ~19-places intermediate for ~12-places in result. The other amazing thing about epow is that, with fractions the most-significant digits of the answer first come early. And since the '-e' scaling is not real floating-point, we actually have a variable-precision floating-point, that lets us do such problems using -e2 or -e10000. See the epow help for better examples. iq+ knocks out some really big players with the above example.

All of iq's addition and mutliplication is done using those same on-paper-type methods -'line up the decimal points' implies padding frations till equal length, etc. But with long numbers, the chunking methods turn what is a digit-by-digit method into wide-column-by-wide-column method. mul was a breakthrough because it handles chunks of variable size -convenient and tricky. Subtraction of long numbers was tricky too -the borrow/carry problem chunk-sized. There again, 'add' uses some stuff I've never seen anywhere -can you see why we prepend a number to every chunk, usually '1', but for subtraction '3' or ''2? And, notice that this won't work for multiplication in a simple way, which means that zeros in the middle of long numbers get nulled during intermediate ops.

That's enough for now, I'm trying to streamline handling of faulty inputs in a way so that it could easily be commented out to save time -I mean so that someone who wanted to use iq in scripts could easily comment out the worst 'speed-bumps' in iq, without breaking anything. Keep it coming guys -you are helping create magic.

[amigo]

Just one more bit - in math everything boils down to increment/decrement -everything reduces to addition. For any iq function, if the numbers are really long, it will be done ~entirely by +/+ (even mul chunking uses add for every column). pow is superfluous for integer exponents, but as soon as you do x^1.???, we have to call nroot -each digit of precision in ??? will require trying the digits 1-9 , by using fpow to raise to 1,000 power. This is why the existing pow recommends no more than 3-places -if you ask for more it will take years for an answer and will be wrong. The new pow4 is, instead, limited by the integer value of the base, plus the integer value of the exponent. An easy way to think of it is as pi-scale -under 3.2^3.2 you can get good answers to maybe 7-11 places. with 1.??whatever you can do ^much-more. And with base 0.???? you could do ^very-large. Usually, people don't use pow for very large numbers, so being limited by absolute input values is a better choice. I'm glad that I haven't rushed to integrate pow4 -the new method replaces about 10 lines with 10 lines, but keeping both means only ~10 more in pow, and still be able to handle stuff like 60058.12341 ^ 5.47.

I never was a mathematician and my last algebra class was over 40 years ago, So I had to learn everything from scratch -plus how to efficiently code that. I didn't know what a logarithm was, nor how to methodically calculate fractional exponents. My hat is off to anyone who wants to figure out this 'tiny' problem of precision math. multiplication and division offer challenges that can't be mastered with addition, so start wtih writing an adder. But, as soon as you get to subtraction, the most logical method will dictate that you 'put the bigger value first' -so your gonna need numeric-comparison also -which is really a lot trickier than it seems. MM, after you first came to this thread, I hurried to fix a long-standing bug in cmp3w -I just new your next 'find' would be: cmp3w -000000000000000000000000000 0.000000000000000000000000 -which at the time would have answered '<'. Unfortunately, fixing that meant 4 new expensive checks -now reduced to 2.

division is famous everywhere for being slow, so multiplication is used where possible. add and mul can be called thousands of times for any seemingly simple problem. Division of long numbers means a bunch of subtractions -the most naive method could mean hours of subtracting. By hand, one uses 'partitioning', so I designed a faster way to automate partitioning -by using multiplication. The point is, every sanity-check we add to add or mul have implications for every other function.

[6502coder]

Here's a modest contribution to the testing. I tested "mul" on 50 pairs of long random numbers. Bottom line: no errors found.

I chose "mul" for the simple reason that I was pretty sure I could quickly crank out a multiplication program that I could reliably use to verify the results from "mul". Using AWK I wrote a program that mimics the pencil-and-paper method of multiplying, with a slight modification to simplify the programming. I wrote another AWK script to generate random pairs of long numbers to use as test input. Finally I wrote a bash script to run "mul" and my AWK multiplier back to back on the same input.

Here's the test driver script "multest.sh":

Code: Select all

awk -f ../../randompair.awk > /tmp/ABfile

. /tmp/ABfile

echo "=========================="
echo $A
echo $B
echo "=========================="

time ./iq mul $A $B

echo "========================================="

time awk -f ../../mult.awk -v A=$A -v B=$B

echo "========================================="
echo "done" 1>&2

randompair.awk generates the two random numbers and assigns them to environment variables "A" and "B". Each number is between 200 and 400 digits long and has a 50-50 chance of containing a decimal point somewhere.

mult.awk is the "by hand" multiplication script.

Here's a typical output from the test script:

Code: Select all

==========================
760522925507318527019001768127255641879178015521746251981101112956147684008121686676679632463516378744531238467596945545778024406830760008024095185198591515128198504035719308339828373.07669489659073445447221
68613217673501424427722619004425987092034285487638775937382025742803685293891582696470676771573219991260216096365316586081250714237428003213869663755196301647010091401451218183785096756944248142686771358633069738095
==========================
52181925033521754821592939319677489558236060258783923583455114150525759948414815292664133854281329786872785542930082637805388960607164025085304620311846645008526842811017787935175082867589849464278948226725498438048204857816366539821188140799657106725051385745113203104062658274918062642413111043290909989058144344244747664545840950679469097552147885310718105467465645234778159985116995885729342182.00820445759468615583995

real	0m7.983s
user	0m5.177s
sys	0m0.500s
=========================================
52181925033521754821592939319677489558236060258783923583455114150525759948414815292664133854281329786872785542930082637805388960607164025085304620311846645008526842811017787935175082867589849464278948226725498438048204857816366539821188140799657106725051385745113203104062658274918062642413111043290909989058144344244747664545840950679469097552147885310718105467465645234778159985116995885729342182.00820445759468615583995

real	0m0.281s
user	0m0.263s
sys	0m0.003s
=========================================
done

I did 50 test runs of "multest.sh" and, aside from the fact "mult.awk" does not trim off extraneous insignificant zeroes, the results from "mul" and "mult.awk" were identical. The tests were done in Slacko 5.8.3 on a 1.3GHz, 1 GB RAM laptop. The AWK in this Slacko is GNU Awk 3.1.8.

Attached is a zip of my AWK files and the test script. Note that you'll have to edit the test script to adjust the pathnames to "iq", "mult.awk", and "randompairs.awk" depending on where you have placed those things.

I hope to tackle "div" or something else more substantial than "mul" next.

[amigo]

Great, multiply 2 200+ digit numbers. I really don't mind the time -the correctness is more important. If time can be improved -even better. Meanwhile I'm writing an exhaustive all-in-one sanity check which fits in the execution block. This will lessen the need for in-function sanity checks. You mentioned a change to fpow -probably short so attach it for my enjoyment tomorrow!

[6502coder]

@amigo

It's explained in the comments to my AWK multiplier program, but as you may not have seen those, let me clarify that the purpose of my testing was not to compare speeds with iq. I wrote my AWK program merely to have a way to verify the results from mul, and speed was not a consideration at all. I chose long numbers only to stress test whatever special methods iq might be using to deal with long numbers. Evidently I've greatly overestimated the extent to which such long numbers actually matter for the intended use cases of iq. (This gets back to my original question about what fields of computation require such large numbers of significant figures, aside from number theory and astronomy.)

We might conveniently divide test cases into two groups: a) syntactically invalid inputs ("garbage inputs"), and b) computationally difficult argument ranges. Personally I have no interest in a); coming up with garbage inputs seems so ad hoc. On the other hand, b) requires a good understanding of how iq works, so as to have a feel where it might be challenged. I haven't studied iq enough to have that understanding.

btw I wasn't the one tinkering with fpow. Perhaps MM?

[amigo]

Sorry about the fpow mixup -I had coded til nearly midnight last nite and just quickly looked here.

Yeah, computationally difficult, like working out the honest computation of the 1000th root of -anything. Anyone can understand that longer strings of digits could, at least, take longer than short numbers. It's maybe not obvious that iq has no access to hardware or libraries which could do provide that. And the specific methods used have to find a 3-way balance between speed, accuracy and usability. What I wanted help with from the start, was help flushing obscure, real errors in long subtractions and in division. div is/was the oldest function and apart from its' dependence on add, for long-length divisions, the method was completely ignoring a couple of classes of numbers. And div was the one I least wanted to work on. It still looks similar to the very old versions -before we were called iq. It uses the same var names, but the method was overhauled from the top -so it was bound to take awhile to get everything right. The only way to do that is to produce errors -till you can't find anymore.

iq is actually one of the most innocent scripts you'll find anywhere -no read/writes/redirects/tmpfiles, no eval, no executions . It was impossible for anything funny to happen -apart from the answers when one disregards the simple usage and syntax. I say 'was', because it could still be abused as an executable: 'iq /bin/ls' would really show you the contents of the CWD. Really innocent. I had to fix that a couple of days ago because I was considering a shout-out to a few Slackers who used to use my old project. And that was a 20,000-line which read and wrote and installed and called
dozens of external binaries, downloaded, uploaded, etc. They were even known to run my software -while logged in as --- root! But, they would have found that huge security-hole right away -not by carelessly trying out (as root): 'iq dd if=/dev/zero of=/dev/sda'. They would have found it by reading the code -but probably after spending a week moaning about coding style, why would I do this, have I tried this other thing, etc. Some of those guys probably have cats, so they know how important local security also is!

The total shell features used in iq is less than 20:

Code: Select all

math unit:
$(()) 		arithmetic operations only with this construction
math operators:
+ - * / %
[ ... -lt,-le.-eq,-ge,-gt,-ne ... ]	numeric comparisons -which is also the math unit

text comparison:
[ .. =,>,< .. ]
[ -z var ]   or [ -n var ]  	check for null or non-null variable

variable assignments
a=val a=$val  a=${var:-defval} 	without or with default values

brackets expansions:
${#var} 	size of var
${foo%bar} and ${foo#bar}	substring extraction - using ? and * 

character classes:
[!0] [!+0-9.-]	only in a couple of places in case statements. like printf -which we do not and will not use, 
			compatibility varies:  [^+0-9.-]	fails under some shells -especially in if constructs

keywords:
if .... then .. elif ... else ... fi 
&& ||		shortcuts to if...else
while .... do ... break ... continue ... done 
case ..... esac  	only clauses ending with ';;'

shell features:
afuncname() {  ..... return  ;} your shell must support functions as we nothing but functions
func 			execute an iq function -since most functions have an 'echo' on return:
a=$( commmand )   command-substitution  _only_ iq functions are called -never an external anything
>&2			redirection of output messages to fd2

shell builtins:
echo  	 no other bultins are used and echo is never used with any options

I just paused above to make that list. Probably missed something worth mentioning and there could be something else in iq+. But that's pretty much it. Keeping the list short is what allows us to run on the 4 most-shells on pcs. Just a couple of day ago I thought -could we run on android/ios shell. And there's still the question about much will run on busybox ash -we might decide to conquer the mobile and IOT markets and reach that global domination we always dreamed of...
I'll go off and work now -it's not important, but if you see and remember something I missed, I'll add it.

[MochiMoppel]

In general, any check anywhere for a special case is a bad idea, when your normal method of processing will catch it.

In your use case it would be a good idea

For mul, we CAN handle zero early, because it WILL change the result to a known value and an exit condition. Since add and mul work on a series of numbers, the fastest method is to handle the inputs one at a time -with a general method.

No, it's not the fastest method. It makes your code slow!
Have you logged and analyzed your function calls? You will see that this "leave it to the normal method" costs you valuable processing time

I'm referring to the most recent example pow -s7 1.357 12.645
pow makes cascading function calls to nroot => nrt_solv => fpow => mul
In above example fpow calls mul 535 times, of which 127 calls are preventable - because the 1st of 2 factors is 1. Being bothered with such a stupid calculation must be felt as an insult by mul, but of course mul knows how to multiply a number with 1 and it does so, slowly, as with any other case since it does not contain an early exit trap that would immediately spill out the result. Expensive indeed. IMO it's the responsibility of the caller to avoid such needless calls, not the responsibility of the function to prepare for them.
Here an example of consecutive fpow calls to mul:

Code: Select all

-s21    1               1.00305742840136
-s21    1.0015275473    1.0015275473
-s21    1               1.00305742800075
-s21    1.0015275474    1.0015275474
-s21    1               1.00305742820106
-s21    1.00152754745   1.00152754745
-s21    1               1.00305742830121

You can see that only the call mul -s$fstprec $out_fst $base_fst sends a '1' and that the '1' is always $out_fst. You can trap this condition and make fpow faster. This is what I used and what seems to work fine:

Code: Select all

[ $((exp_fst%2)) -ne 0 ] && { [ "$out_fst" = 1 ] && out_fst=$base_fst || out_fst=$( mul -s$fstprec $out_fst $base_fst ) ;}

I found an even bigger resource-eater in mul itself, partly explaining why mul is so slow. In above example it calls add 2891 times (by comparison mmul also relies on add but needs only 139 calls). Of these 2891 calls, 1133 calls request the add function to add '0' to a number. Not a good idea. Same as with mul: add is perfectly capable to add zero to a number, but it shouldn't be called for such trivial task. It costs you dearly when speed is your prime concern.

[amigo]

I'm not saying their is no faster way to do anything. I know very well that there are several places to could be optimized. But, first everything has to work correctly -and with numbers longer than 19-digits. mul consists of triple-nested while loops -which are difficult to get right, at best. Are you sure your speedup are staying accurate everywhere.

I'm anxious to see what you've come up with -you mentioned fpow, so show what you are doing there that works without modified mul. Meanwhile, I've been writing a complete front-end execution block should catch everything you have been throwing at iq, like div bla / bla. It will also stop you from doing dangerous things. I've been quite distracted by you with the nonsense inputs. I hoped to get it ready for release, by getting to the bottom of every possible operation to flush out obscure, hard to replicate/understand calculation errors. The syntax is simple -and most be people can understand that if you throw BS at a program, strange, wonderful, or terrible things will happen.

If you want to contribute, your help is welcome -but which project, which is 98% ready, is gonna start messing with the deep internals by trying a lot of stuff at that point? It is still is not all about speed -as we have seen we can often compete head-to-head -and sometimes do what the others don't. I think you may be ignoring the subtleties needed for achieving correct results over a broad range of inputs. If you can create drop-in replacements for any function, they are welcome and could be included in the next release. I'm looking for iq_2.0 which 'just works'. iq_3.0 is a great place for changes to the methods which work better in anyway and that work under our targeted shells.

Maybe the best thing for you to do is write a complete system from scratch. iq is a complete re-write of an earlier, where I had to work out the basics of turning everything into an integer problem, finding the features/methods which would work apart from bash. That first write was deadly slow -and could do no series calculations like iq's add and mul do. I worked out the chunking method by writing a binary calculator and dec-bin-dec convertor. The point is that it took a complete re-write to improve the speed, range and re-design the workflow to allow series calculations.

From the start, it seemed more like you were making fun of me or my project. You would not respect the usage and made incomplete, untested suggestions. And, you admitted that you didn't understand why a division would involve subtraction, and that you thought that pow 'might' be calling mul. But then, when someone who understands math says iq is 'amazing', you suddenly change from a prankster to a ... what? Any shell script is a delicate thing -one single changed character can spoil the whole thing. Do you understand why ipow/epow need log, and the enormous task that nrt_solv has to calculate a given root? Even with a much faster mul/fpow, solving a fractional-exponent is still gonna be the Achilles-heel of pow -because that means solving roots.

The methods I am using now are not the first way I have found or tried. And they certainly are not the only possible ways. I've always worked out first, a way to do an honest calculation without using approximations -which are usually range-limited and usually only achieve accuracy by doing many iterations at large scales. The details about special cases and where best to handle them have implications in the function's structure and procedures -sometimes the flow has to be changed just because of them. For some ops, they can be handled without doing that and that's where optimizations of a method can be done easily, without causing 'ripples' through the other functions. And that's where completely new methods can be tried.

I really don't want to argue or explain anymore. Every time something comes up, I have to tried to address it, fix it as suggested, test the _users_ code, or explain why it won't easily work -and put lots of comments in the code about it all, change any documents/help which are affected. So that the user can follow the flow, learn how it fits together, and if they know about math, suggest workable changes to the mathematical methods. There are quite a few big reasons that, seemingly, no one has been able to get this far with a calculator written in shell. Can you solve e^(-x), with non-integer 'x', using code which you wrote from scratch and not relying on someone else's examples. I just wanted to play with some ai stuff in shell-only. I looked a lot for an existing calculator written in shell -and to this day have found or been shown anything that approaches iq. There are a couple which will 4-ops for numbers that fit the shell-math limits, hundreds which call bc/awk/other for any heavy work. Show us your code.

[amigo]

So, I've had my name is the linux ChangeLog twice. Do you suppose that happened by writing to the LKML with questions that show I don't understand how it works, with suggestions for changes -but no patches to show what I mean? Or by criticizing their unique coding-style rules? No one will even look at your changes unless you send a perfectly-formatted diff which applies without glitches to a known version of the source. My changes also needed changes to the documentation -no one there was going to pretty-up and complete MY submission so that it would work and be complete. And they certainly were not going to do anything if I started trying to turn the monolithic kernel into a micro-kernel, submit changes to a critical area or changes that are untested.

So, show me your '-pu'-style diffs so I can review your changes. Maybe everyone of them can be applied immediately -but if you don't really understand what is going on with the code, how could I blindly apply your changes and expect an improvement of the total product? I've tried and tested a lot of stuff which you will not think of for years to come. Yes, 0's and 1's are often a special case, but this is not a binary process and there are 8 more digits in our base10 -which must be handled with a method. Optimization of code is the very last step -not the first.
You are right about this:

IMO it's the responsibility of the caller to avoid such needless calls, not the responsibility of the function to prepare for them.

But I find it _rich_ that you say this now, after the way you started. Is that not what I should have told you from the first post, instead of trying to explain?