 |
| Sample output from MathLibrary.cmd |
- Windows Batch Script only supports 32-bit signed integers. This bounds its native math functionality from -2,147,483,648 to 2,147,483,647, inclusively.
- Windows Batch Script does not handle decimal points at all.
- Windows Batch Script's native arithmetic functions are extremely limited.
- Windows Batch Script has almost no error handling capabilities at all. They're so bad, in fact, that you can oftentimes run afoul of each of the above limitations and never receive an error for doing so - you'll just get undesired results.
To that end, I started working on a way to broaden its capabilities a bit, and in the spirit of the original goal of implementing Project Euler solutions using nothing but Windows Batch Scripting, I decided to keep my solution confined to Windows Batch Scripting as well. At first I did what any good sysadmin would do and tried to Google the problem away, which led to some fruitful results. Someone found a way to calculate Pi using Batch Script, which was encouraging - that proved floating point math was possible. I also found solutions that allowed arbitrary length integers to be calculated, which were also promising. Unfortunately, when I attempted to apply those solutions to my particular problem, I found that the code wasn't particularly portable (the division subroutine in the Pi script, for example, only works as long as one of the digits is within the 32-bit signed limit) or otherwise useful for my needs. Consequently, it looked like I would have to write my own.
Now, before anyone gets excited, it's not done yet. I'm publishing it now because 2015 is here, I've been fiddling with this on and off for the past two months, and I decided it was high time to just get it out the door for the rest of the world. With that in mind, here are the current limitations of MathLibrary.cmd:
- Negative numbers are only supported for addition, subtraction, and comparison. Multiplication and division are coming soon.
- The algorithms are "conceptual", meaning that, if you were a 10-year-old elementary school student that could read Windows Batch Script, you would understand what was going on perfectly. I'm not taking advantages of quads and octs yet (I'll explain why below).
- It's slow. Two 500 digit numbers take about 10 seconds to add on my laptop (AMD Phenom II N660 3.0 GHz) and about 25 seconds to subtract. Two 50 digit numbers take about a minute and a half to multiply together. Division is unspeakably atrocious.
That said, it does successfully add, subtract, multiply, divide, and compare arbitrary-length floating point numbers, which is pretty cool. It can be done.
So, let's talk about speed for a bit. While working on the script, I decided to experiment with refactoring the addition subroutined (:ExtAdd) to use eight digit blocks instead of single integer blocks like what you see on GitHub. What I discovered was that, in order to do so, I had to check for blocks that started with a 0 - or several 0's - and filter them out, otherwise Windows Batch Script would assume I wanted to add two octal numbers together. Consequently, whatever performance gains I got out of adding in 8-digit blocks instead of single digits was devoured by the time it took to clear out the leading 0's out of the blocks so they would add together cleanly.
Another odd note - take a look at the code used in the Pi script for adding two digits together:
set /a Add_Digit = Add_Carry + %1_%%i + %2_%%i
set /a %1_%%i = Add_Digit %% 10000
set /a Add_Carry = Add_Digit / 10000
Now, let's compare to my equivalent code:
SET /A _AddByPos=_AddInt1+_AddInt2+_AddCarry
IF !_AddByPos! GEQ 10 (
SET _AddCarry=1
SET /A _AddByPos-=10
) ELSE (
SET _AddCarry=0
)
What's the difference? The Pi script algorithm is conceptually pretty clever - it takes advantage of the fact that Windows Batch Script's division operator will only return the integer value of a divide operation (i.e. everything to the left of the decimal point in the result). Consequently, if you divide a number between 10-19, inclusively, by 10, you will get 1 instead of 1.1, 1.2, 1.3, and so on. Then, you can use the modulus operator to get the remainder, which, when dividing by 10, would be the lone digit to the right of the decimal point (e.g. 11 %% 10 = 1, 12 %% 10 = 2, and so on).
It's also slower.
Using my UnitTest.cmd script, which I use to make sure that improvements to the script don't fundamentally break the script, here's the times I got for performing the first 10 addition tests using my method (time elapsed in bold):
01 OK 21:01:50.42 21:01:50.32 0:0:0.10
02 OK 21:01:50.51 21:01:50.44 0:0:0.7
03 OK 21:01:50.61 21:01:50.52 0:0:0.9
04 OK 21:01:50.73 21:01:50.62 0:0:0.11
05 OK 21:01:50.87 21:01:50.74 0:0:0.13
06 OK 21:01:51.19 21:01:50.88 0:0:0.31
07 OK 21:01:51.57 21:01:51.21 0:0:0.36
08 OK 21:01:52.91 21:01:51.59 0:0:1.32
09 OK 21:01:55.01 21:01:52.92 0:0:2.9
10 OK 21:02:05.95 21:01:55.08 0:0:10.87
And here's what I got when I implemented the Pi script algorithm:
01 OK 21:48:31.13 21:48:31.02 0:0:0.11
02 OK 21:48:31.24 21:48:31.15 0:0:0.9
03 OK 21:48:31.37 21:48:31.26 0:0:0.11
04 OK 21:48:31.58 21:48:31.40 0:0:0.18
05 OK 21:48:31.77 21:48:31.60 0:0:0.17
06 OK 21:48:32.11 21:48:31.79 0:0:0.32
07 OK 21:48:32.63 21:48:32.13 0:0:0.50
08 OK 21:48:34.21 21:48:32.65 0:0:1.56
09 OK 21:48:37.11 21:48:34.22 0:0:2.89
10 OK 21:48:50.02 21:48:37.12 0:0:12.90
Note that most of the tests are considerably slower - about 10-20% slower, give or take. Why? Part of the problem is that Windows Batch Script's internal math functions are unevenly implemented - addition and subtraction, which my method uses, is faster than division or the modulus operator. Part of it is that the Pi script algorithm applies the same three steps to all addition operations - add, divide, modulus - while mine oftentimes (especially in the first 10 unit tests, which are solely large number addition with no carry) only uses two operations (add, set), with a third set (subtract by 10) used only when there's a carry operation in play.
Ah... but what about that IF statement? Doesn't that count as an operation?
It does, actually, which is why my method is only 10-20% faster instead of 33% faster under ideal conditions, which the first ten unit tests simulate nicely. However, every time the Windows Batch Script arithmetic engine is called, it noticeably kills performance. How noticeably? When I first started this script, I intentionally set all of my "integers" using SET /A to help me differentiate in my code between the strings and substrings I was manipulating against actual numbers that Windows Batch Script could manipulate. While working on it, however, I read somewhere that SET /A added a step in the interpreter over just using SET, so I put it to the test and converted all of my SET /A declarations to SET. The result was a 5-10% performance improvement.
So there you have it. Like I said, I'm not done fiddling with this - negative number support will be coming to multiplication and division over the next week or two, depending on time and motivation. After that, I'm probably going to mix up the UnitTest script a bit so I can test individual components in a hurry instead of testing ALL THE THINGS all the time - the multiplication tests in particular really slow me down - and then I'm going to start playing with performance tuning the script as much as possible. Assuming I can get division into something resembling "usable condition" (it takes over 10 seconds to divide 1 by 3), I'll then start implementing a square root subroutine, which will then clear the way for me to get back to work on Project Euler solutions once more.
It'll get there, one line at a time. I just have to make this script suck a little bit less each week, that's all. It's a good metaphor for life.
SET /A _AddByPos=_AddInt1+_AddInt2+_AddCarry
IF !_AddByPos! GEQ 10 (
SET _AddCarry=1
SET /A _AddByPos-=10
) ELSE (
SET _AddCarry=0
)
What's the difference? The Pi script algorithm is conceptually pretty clever - it takes advantage of the fact that Windows Batch Script's division operator will only return the integer value of a divide operation (i.e. everything to the left of the decimal point in the result). Consequently, if you divide a number between 10-19, inclusively, by 10, you will get 1 instead of 1.1, 1.2, 1.3, and so on. Then, you can use the modulus operator to get the remainder, which, when dividing by 10, would be the lone digit to the right of the decimal point (e.g. 11 %% 10 = 1, 12 %% 10 = 2, and so on).
It's also slower.
Using my UnitTest.cmd script, which I use to make sure that improvements to the script don't fundamentally break the script, here's the times I got for performing the first 10 addition tests using my method (time elapsed in bold):
01 OK 21:01:50.42 21:01:50.32 0:0:0.10
02 OK 21:01:50.51 21:01:50.44 0:0:0.7
03 OK 21:01:50.61 21:01:50.52 0:0:0.9
04 OK 21:01:50.73 21:01:50.62 0:0:0.11
05 OK 21:01:50.87 21:01:50.74 0:0:0.13
06 OK 21:01:51.19 21:01:50.88 0:0:0.31
07 OK 21:01:51.57 21:01:51.21 0:0:0.36
08 OK 21:01:52.91 21:01:51.59 0:0:1.32
09 OK 21:01:55.01 21:01:52.92 0:0:2.9
10 OK 21:02:05.95 21:01:55.08 0:0:10.87
And here's what I got when I implemented the Pi script algorithm:
01 OK 21:48:31.13 21:48:31.02 0:0:0.11
02 OK 21:48:31.24 21:48:31.15 0:0:0.9
03 OK 21:48:31.37 21:48:31.26 0:0:0.11
04 OK 21:48:31.58 21:48:31.40 0:0:0.18
05 OK 21:48:31.77 21:48:31.60 0:0:0.17
06 OK 21:48:32.11 21:48:31.79 0:0:0.32
07 OK 21:48:32.63 21:48:32.13 0:0:0.50
08 OK 21:48:34.21 21:48:32.65 0:0:1.56
09 OK 21:48:37.11 21:48:34.22 0:0:2.89
10 OK 21:48:50.02 21:48:37.12 0:0:12.90
Note that most of the tests are considerably slower - about 10-20% slower, give or take. Why? Part of the problem is that Windows Batch Script's internal math functions are unevenly implemented - addition and subtraction, which my method uses, is faster than division or the modulus operator. Part of it is that the Pi script algorithm applies the same three steps to all addition operations - add, divide, modulus - while mine oftentimes (especially in the first 10 unit tests, which are solely large number addition with no carry) only uses two operations (add, set), with a third set (subtract by 10) used only when there's a carry operation in play.
Ah... but what about that IF statement? Doesn't that count as an operation?
It does, actually, which is why my method is only 10-20% faster instead of 33% faster under ideal conditions, which the first ten unit tests simulate nicely. However, every time the Windows Batch Script arithmetic engine is called, it noticeably kills performance. How noticeably? When I first started this script, I intentionally set all of my "integers" using SET /A to help me differentiate in my code between the strings and substrings I was manipulating against actual numbers that Windows Batch Script could manipulate. While working on it, however, I read somewhere that SET /A added a step in the interpreter over just using SET, so I put it to the test and converted all of my SET /A declarations to SET. The result was a 5-10% performance improvement.
So there you have it. Like I said, I'm not done fiddling with this - negative number support will be coming to multiplication and division over the next week or two, depending on time and motivation. After that, I'm probably going to mix up the UnitTest script a bit so I can test individual components in a hurry instead of testing ALL THE THINGS all the time - the multiplication tests in particular really slow me down - and then I'm going to start playing with performance tuning the script as much as possible. Assuming I can get division into something resembling "usable condition" (it takes over 10 seconds to divide 1 by 3), I'll then start implementing a square root subroutine, which will then clear the way for me to get back to work on Project Euler solutions once more.
It'll get there, one line at a time. I just have to make this script suck a little bit less each week, that's all. It's a good metaphor for life.
No comments:
Post a Comment