diff options
Diffstat (limited to 'examples/shellmath')
| -rw-r--r-- | examples/shellmath/LICENSE | 677 | ||||
| -rw-r--r-- | examples/shellmath/README.md | 166 | ||||
| -rw-r--r-- | examples/shellmath/assert.sh | 85 | ||||
| -rw-r--r-- | examples/shellmath/faster_e_demo.sh | 68 | ||||
| -rw-r--r-- | examples/shellmath/image.png | bin | 0 -> 48779 bytes | |||
| -rw-r--r-- | examples/shellmath/runTests.sh | 124 | ||||
| -rw-r--r-- | examples/shellmath/shellmath.sh | 1068 | ||||
| -rw-r--r-- | examples/shellmath/slower_e_demo.sh | 55 | ||||
| -rw-r--r-- | examples/shellmath/testCases.in | 142 | ||||
| -rw-r--r-- | examples/shellmath/timingData.txt | 42 |
10 files changed, 2427 insertions, 0 deletions
diff --git a/examples/shellmath/LICENSE b/examples/shellmath/LICENSE new file mode 100644 index 0000000..e3bf3bb --- /dev/null +++ b/examples/shellmath/LICENSE @@ -0,0 +1,677 @@ +Shellfloat is copyright (c) 2020 by Michael Wood. +================================================================================ + + GNU GENERAL PUBLIC LICENSE + Version 3, 29 June 2007 + + Copyright (C) 2007 Free Software Foundation, Inc. <https://fsf.org/> + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The GNU General Public License is a free, copyleft license for +software and other kinds of works. + + The licenses for most software and other practical works are designed +to take away your freedom to share and change the works. By contrast, +the GNU General Public License is intended to guarantee your freedom to +share and change all versions of a program--to make sure it remains free +software for all its users. We, the Free Software Foundation, use the +GNU General Public License for most of our software; it applies also to +any other work released this way by its authors. You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +them if you wish), that you receive source code or can get it if you +want it, that you can change the software or use pieces of it in new +free programs, and that you know you can do these things. + + To protect your rights, we need to prevent others from denying you +these rights or asking you to surrender the rights. Therefore, you have +certain responsibilities if you distribute copies of the software, or if +you modify it: responsibilities to respect the freedom of others. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must pass on to the recipients the same +freedoms that you received. You must make sure that they, too, receive +or can get the source code. And you must show them these terms so they +know their rights. + + Developers that use the GNU GPL protect your rights with two steps: +(1) assert copyright on the software, and (2) offer you this License +giving you legal permission to copy, distribute and/or modify it. + + For the developers' and authors' protection, the GPL clearly explains +that there is no warranty for this free software. For both users' and +authors' sake, the GPL requires that modified versions be marked as +changed, so that their problems will not be attributed erroneously to +authors of previous versions. + + Some devices are designed to deny users access to install or run +modified versions of the software inside them, although the manufacturer +can do so. This is fundamentally incompatible with the aim of +protecting users' freedom to change the software. The systematic +pattern of such abuse occurs in the area of products for individuals to +use, which is precisely where it is most unacceptable. Therefore, we +have designed this version of the GPL to prohibit the practice for those +products. If such problems arise substantially in other domains, we +stand ready to extend this provision to those domains in future versions +of the GPL, as needed to protect the freedom of users. + + Finally, every program is threatened constantly by software patents. +States should not allow patents to restrict development and use of +software on general-purpose computers, but in those that do, we wish to +avoid the special danger that patents applied to a free program could +make it effectively proprietary. To prevent this, the GPL assures that +patents cannot be used to render the program non-free. + + The precise terms and conditions for copying, distribution and +modification follow. + + TERMS AND CONDITIONS + + 0. Definitions. + + "This License" refers to version 3 of the GNU General Public License. + + "Copyright" also means copyright-like laws that apply to other kinds of +works, such as semiconductor masks. + + "The Program" refers to any copyrightable work licensed under this +License. Each licensee is addressed as "you". "Licensees" and +"recipients" may be individuals or organizations. + + To "modify" a work means to copy from or adapt all or part of the work +in a fashion requiring copyright permission, other than the making of an +exact copy. The resulting work is called a "modified version" of the +earlier work or a work "based on" the earlier work. + + A "covered work" means either the unmodified Program or a work based +on the Program. + + To "propagate" a work means to do anything with it that, without +permission, would make you directly or secondarily liable for +infringement under applicable copyright law, except executing it on a +computer or modifying a private copy. Propagation includes copying, +distribution (with or without modification), making available to the +public, and in some countries other activities as well. + + To "convey" a work means any kind of propagation that enables other +parties to make or receive copies. Mere interaction with a user through +a computer network, with no transfer of a copy, is not conveying. + + An interactive user interface displays "Appropriate Legal Notices" +to the extent that it includes a convenient and prominently visible +feature that (1) displays an appropriate copyright notice, and (2) +tells the user that there is no warranty for the work (except to the +extent that warranties are provided), that licensees may convey the +work under this License, and how to view a copy of this License. If +the interface presents a list of user commands or options, such as a +menu, a prominent item in the list meets this criterion. + + 1. Source Code. + + The "source code" for a work means the preferred form of the work +for making modifications to it. "Object code" means any non-source +form of a work. + + A "Standard Interface" means an interface that either is an official +standard defined by a recognized standards body, or, in the case of +interfaces specified for a particular programming language, one that +is widely used among developers working in that language. + + The "System Libraries" of an executable work include anything, other +than the work as a whole, that (a) is included in the normal form of +packaging a Major Component, but which is not part of that Major +Component, and (b) serves only to enable use of the work with that +Major Component, or to implement a Standard Interface for which an +implementation is available to the public in source code form. A +"Major Component", in this context, means a major essential component +(kernel, window system, and so on) of the specific operating system +(if any) on which the executable work runs, or a compiler used to +produce the work, or an object code interpreter used to run it. + + The "Corresponding Source" for a work in object code form means all +the source code needed to generate, install, and (for an executable +work) run the object code and to modify the work, including scripts to +control those activities. However, it does not include the work's +System Libraries, or general-purpose tools or generally available free +programs which are used unmodified in performing those activities but +which are not part of the work. For example, Corresponding Source +includes interface definition files associated with source files for +the work, and the source code for shared libraries and dynamically +linked subprograms that the work is specifically designed to require, +such as by intimate data communication or control flow between those +subprograms and other parts of the work. + + The Corresponding Source need not include anything that users +can regenerate automatically from other parts of the Corresponding +Source. + + The Corresponding Source for a work in source code form is that +same work. + + 2. Basic Permissions. + + All rights granted under this License are granted for the term of +copyright on the Program, and are irrevocable provided the stated +conditions are met. This License explicitly affirms your unlimited +permission to run the unmodified Program. The output from running a +covered work is covered by this License only if the output, given its +content, constitutes a covered work. This License acknowledges your +rights of fair use or other equivalent, as provided by copyright law. + + You may make, run and propagate covered works that you do not +convey, without conditions so long as your license otherwise remains +in force. You may convey covered works to others for the sole purpose +of having them make modifications exclusively for you, or provide you +with facilities for running those works, provided that you comply with +the terms of this License in conveying all material for which you do +not control copyright. Those thus making or running the covered works +for you must do so exclusively on your behalf, under your direction +and control, on terms that prohibit them from making any copies of +your copyrighted material outside their relationship with you. + + Conveying under any other circumstances is permitted solely under +the conditions stated below. Sublicensing is not allowed; section 10 +makes it unnecessary. + + 3. Protecting Users' Legal Rights From Anti-Circumvention Law. + + No covered work shall be deemed part of an effective technological +measure under any applicable law fulfilling obligations under article +11 of the WIPO copyright treaty adopted on 20 December 1996, or +similar laws prohibiting or restricting circumvention of such +measures. + + When you convey a covered work, you waive any legal power to forbid +circumvention of technological measures to the extent such circumvention +is effected by exercising rights under this License with respect to +the covered work, and you disclaim any intention to limit operation or +modification of the work as a means of enforcing, against the work's +users, your or third parties' legal rights to forbid circumvention of +technological measures. + + 4. Conveying Verbatim Copies. + + You may convey verbatim copies of the Program's source code as you +receive it, in any medium, provided that you conspicuously and +appropriately publish on each copy an appropriate copyright notice; +keep intact all notices stating that this License and any +non-permissive terms added in accord with section 7 apply to the code; +keep intact all notices of the absence of any warranty; and give all +recipients a copy of this License along with the Program. + + You may charge any price or no price for each copy that you convey, +and you may offer support or warranty protection for a fee. + + 5. Conveying Modified Source Versions. + + You may convey a work based on the Program, or the modifications to +produce it from the Program, in the form of source code under the +terms of section 4, provided that you also meet all of these conditions: + + a) The work must carry prominent notices stating that you modified + it, and giving a relevant date. + + b) The work must carry prominent notices stating that it is + released under this License and any conditions added under section + 7. This requirement modifies the requirement in section 4 to + "keep intact all notices". + + c) You must license the entire work, as a whole, under this + License to anyone who comes into possession of a copy. This + License will therefore apply, along with any applicable section 7 + additional terms, to the whole of the work, and all its parts, + regardless of how they are packaged. This License gives no + permission to license the work in any other way, but it does not + invalidate such permission if you have separately received it. + + d) If the work has interactive user interfaces, each must display + Appropriate Legal Notices; however, if the Program has interactive + interfaces that do not display Appropriate Legal Notices, your + work need not make them do so. + + A compilation of a covered work with other separate and independent +works, which are not by their nature extensions of the covered work, +and which are not combined with it such as to form a larger program, +in or on a volume of a storage or distribution medium, is called an +"aggregate" if the compilation and its resulting copyright are not +used to limit the access or legal rights of the compilation's users +beyond what the individual works permit. Inclusion of a covered work +in an aggregate does not cause this License to apply to the other +parts of the aggregate. + + 6. Conveying Non-Source Forms. + + You may convey a covered work in object code form under the terms +of sections 4 and 5, provided that you also convey the +machine-readable Corresponding Source under the terms of this License, +in one of these ways: + + a) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by the + Corresponding Source fixed on a durable physical medium + customarily used for software interchange. + + b) Convey the object code in, or embodied in, a physical product + (including a physical distribution medium), accompanied by a + written offer, valid for at least three years and valid for as + long as you offer spare parts or customer support for that product + model, to give anyone who possesses the object code either (1) a + copy of the Corresponding Source for all the software in the + product that is covered by this License, on a durable physical + medium customarily used for software interchange, for a price no + more than your reasonable cost of physically performing this + conveying of source, or (2) access to copy the + Corresponding Source from a network server at no charge. + + c) Convey individual copies of the object code with a copy of the + written offer to provide the Corresponding Source. This + alternative is allowed only occasionally and noncommercially, and + only if you received the object code with such an offer, in accord + with subsection 6b. + + d) Convey the object code by offering access from a designated + place (gratis or for a charge), and offer equivalent access to the + Corresponding Source in the same way through the same place at no + further charge. You need not require recipients to copy the + Corresponding Source along with the object code. If the place to + copy the object code is a network server, the Corresponding Source + may be on a different server (operated by you or a third party) + that supports equivalent copying facilities, provided you maintain + clear directions next to the object code saying where to find the + Corresponding Source. Regardless of what server hosts the + Corresponding Source, you remain obligated to ensure that it is + available for as long as needed to satisfy these requirements. + + e) Convey the object code using peer-to-peer transmission, provided + you inform other peers where the object code and Corresponding + Source of the work are being offered to the general public at no + charge under subsection 6d. + + A separable portion of the object code, whose source code is excluded +from the Corresponding Source as a System Library, need not be +included in conveying the object code work. + + A "User Product" is either (1) a "consumer product", which means any +tangible personal property which is normally used for personal, family, +or household purposes, or (2) anything designed or sold for incorporation +into a dwelling. In determining whether a product is a consumer product, +doubtful cases shall be resolved in favor of coverage. For a particular +product received by a particular user, "normally used" refers to a +typical or common use of that class of product, regardless of the status +of the particular user or of the way in which the particular user +actually uses, or expects or is expected to use, the product. A product +is a consumer product regardless of whether the product has substantial +commercial, industrial or non-consumer uses, unless such uses represent +the only significant mode of use of the product. + + "Installation Information" for a User Product means any methods, +procedures, authorization keys, or other information required to install +and execute modified versions of a covered work in that User Product from +a modified version of its Corresponding Source. The information must +suffice to ensure that the continued functioning of the modified object +code is in no case prevented or interfered with solely because +modification has been made. + + If you convey an object code work under this section in, or with, or +specifically for use in, a User Product, and the conveying occurs as +part of a transaction in which the right of possession and use of the +User Product is transferred to the recipient in perpetuity or for a +fixed term (regardless of how the transaction is characterized), the +Corresponding Source conveyed under this section must be accompanied +by the Installation Information. But this requirement does not apply +if neither you nor any third party retains the ability to install +modified object code on the User Product (for example, the work has +been installed in ROM). + + The requirement to provide Installation Information does not include a +requirement to continue to provide support service, warranty, or updates +for a work that has been modified or installed by the recipient, or for +the User Product in which it has been modified or installed. Access to a +network may be denied when the modification itself materially and +adversely affects the operation of the network or violates the rules and +protocols for communication across the network. + + Corresponding Source conveyed, and Installation Information provided, +in accord with this section must be in a format that is publicly +documented (and with an implementation available to the public in +source code form), and must require no special password or key for +unpacking, reading or copying. + + 7. Additional Terms. + + "Additional permissions" are terms that supplement the terms of this +License by making exceptions from one or more of its conditions. +Additional permissions that are applicable to the entire Program shall +be treated as though they were included in this License, to the extent +that they are valid under applicable law. If additional permissions +apply only to part of the Program, that part may be used separately +under those permissions, but the entire Program remains governed by +this License without regard to the additional permissions. + + When you convey a copy of a covered work, you may at your option +remove any additional permissions from that copy, or from any part of +it. (Additional permissions may be written to require their own +removal in certain cases when you modify the work.) You may place +additional permissions on material, added by you to a covered work, +for which you have or can give appropriate copyright permission. + + Notwithstanding any other provision of this License, for material you +add to a covered work, you may (if authorized by the copyright holders of +that material) supplement the terms of this License with terms: + + a) Disclaiming warranty or limiting liability differently from the + terms of sections 15 and 16 of this License; or + + b) Requiring preservation of specified reasonable legal notices or + author attributions in that material or in the Appropriate Legal + Notices displayed by works containing it; or + + c) Prohibiting misrepresentation of the origin of that material, or + requiring that modified versions of such material be marked in + reasonable ways as different from the original version; or + + d) Limiting the use for publicity purposes of names of licensors or + authors of the material; or + + e) Declining to grant rights under trademark law for use of some + trade names, trademarks, or service marks; or + + f) Requiring indemnification of licensors and authors of that + material by anyone who conveys the material (or modified versions of + it) with contractual assumptions of liability to the recipient, for + any liability that these contractual assumptions directly impose on + those licensors and authors. + + All other non-permissive additional terms are considered "further +restrictions" within the meaning of section 10. If the Program as you +received it, or any part of it, contains a notice stating that it is +governed by this License along with a term that is a further +restriction, you may remove that term. If a license document contains +a further restriction but permits relicensing or conveying under this +License, you may add to a covered work material governed by the terms +of that license document, provided that the further restriction does +not survive such relicensing or conveying. + + If you add terms to a covered work in accord with this section, you +must place, in the relevant source files, a statement of the +additional terms that apply to those files, or a notice indicating +where to find the applicable terms. + + Additional terms, permissive or non-permissive, may be stated in the +form of a separately written license, or stated as exceptions; +the above requirements apply either way. + + 8. Termination. + + You may not propagate or modify a covered work except as expressly +provided under this License. Any attempt otherwise to propagate or +modify it is void, and will automatically terminate your rights under +this License (including any patent licenses granted under the third +paragraph of section 11). + + However, if you cease all violation of this License, then your +license from a particular copyright holder is reinstated (a) +provisionally, unless and until the copyright holder explicitly and +finally terminates your license, and (b) permanently, if the copyright +holder fails to notify you of the violation by some reasonable means +prior to 60 days after the cessation. + + Moreover, your license from a particular copyright holder is +reinstated permanently if the copyright holder notifies you of the +violation by some reasonable means, this is the first time you have +received notice of violation of this License (for any work) from that +copyright holder, and you cure the violation prior to 30 days after +your receipt of the notice. + + Termination of your rights under this section does not terminate the +licenses of parties who have received copies or rights from you under +this License. If your rights have been terminated and not permanently +reinstated, you do not qualify to receive new licenses for the same +material under section 10. + + 9. Acceptance Not Required for Having Copies. + + You are not required to accept this License in order to receive or +run a copy of the Program. Ancillary propagation of a covered work +occurring solely as a consequence of using peer-to-peer transmission +to receive a copy likewise does not require acceptance. However, +nothing other than this License grants you permission to propagate or +modify any covered work. These actions infringe copyright if you do +not accept this License. Therefore, by modifying or propagating a +covered work, you indicate your acceptance of this License to do so. + + 10. Automatic Licensing of Downstream Recipients. + + Each time you convey a covered work, the recipient automatically +receives a license from the original licensors, to run, modify and +propagate that work, subject to this License. You are not responsible +for enforcing compliance by third parties with this License. + + An "entity transaction" is a transaction transferring control of an +organization, or substantially all assets of one, or subdividing an +organization, or merging organizations. If propagation of a covered +work results from an entity transaction, each party to that +transaction who receives a copy of the work also receives whatever +licenses to the work the party's predecessor in interest had or could +give under the previous paragraph, plus a right to possession of the +Corresponding Source of the work from the predecessor in interest, if +the predecessor has it or can get it with reasonable efforts. + + You may not impose any further restrictions on the exercise of the +rights granted or affirmed under this License. For example, you may +not impose a license fee, royalty, or other charge for exercise of +rights granted under this License, and you may not initiate litigation +(including a cross-claim or counterclaim in a lawsuit) alleging that +any patent claim is infringed by making, using, selling, offering for +sale, or importing the Program or any portion of it. + + 11. Patents. + + A "contributor" is a copyright holder who authorizes use under this +License of the Program or a work on which the Program is based. The +work thus licensed is called the contributor's "contributor version". + + A contributor's "essential patent claims" are all patent claims +owned or controlled by the contributor, whether already acquired or +hereafter acquired, that would be infringed by some manner, permitted +by this License, of making, using, or selling its contributor version, +but do not include claims that would be infringed only as a +consequence of further modification of the contributor version. For +purposes of this definition, "control" includes the right to grant +patent sublicenses in a manner consistent with the requirements of +this License. + + Each contributor grants you a non-exclusive, worldwide, royalty-free +patent license under the contributor's essential patent claims, to +make, use, sell, offer for sale, import and otherwise run, modify and +propagate the contents of its contributor version. + + In the following three paragraphs, a "patent license" is any express +agreement or commitment, however denominated, not to enforce a patent +(such as an express permission to practice a patent or covenant not to +sue for patent infringement). To "grant" such a patent license to a +party means to make such an agreement or commitment not to enforce a +patent against the party. + + If you convey a covered work, knowingly relying on a patent license, +and the Corresponding Source of the work is not available for anyone +to copy, free of charge and under the terms of this License, through a +publicly available network server or other readily accessible means, +then you must either (1) cause the Corresponding Source to be so +available, or (2) arrange to deprive yourself of the benefit of the +patent license for this particular work, or (3) arrange, in a manner +consistent with the requirements of this License, to extend the patent +license to downstream recipients. "Knowingly relying" means you have +actual knowledge that, but for the patent license, your conveying the +covered work in a country, or your recipient's use of the covered work +in a country, would infringe one or more identifiable patents in that +country that you have reason to believe are valid. + + If, pursuant to or in connection with a single transaction or +arrangement, you convey, or propagate by procuring conveyance of, a +covered work, and grant a patent license to some of the parties +receiving the covered work authorizing them to use, propagate, modify +or convey a specific copy of the covered work, then the patent license +you grant is automatically extended to all recipients of the covered +work and works based on it. + + A patent license is "discriminatory" if it does not include within +the scope of its coverage, prohibits the exercise of, or is +conditioned on the non-exercise of one or more of the rights that are +specifically granted under this License. You may not convey a covered +work if you are a party to an arrangement with a third party that is +in the business of distributing software, under which you make payment +to the third party based on the extent of your activity of conveying +the work, and under which the third party grants, to any of the +parties who would receive the covered work from you, a discriminatory +patent license (a) in connection with copies of the covered work +conveyed by you (or copies made from those copies), or (b) primarily +for and in connection with specific products or compilations that +contain the covered work, unless you entered into that arrangement, +or that patent license was granted, prior to 28 March 2007. + + Nothing in this License shall be construed as excluding or limiting +any implied license or other defenses to infringement that may +otherwise be available to you under applicable patent law. + + 12. No Surrender of Others' Freedom. + + If conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot convey a +covered work so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you may +not convey it at all. For example, if you agree to terms that obligate you +to collect a royalty for further conveying from those to whom you convey +the Program, the only way you could satisfy both those terms and this +License would be to refrain entirely from conveying the Program. + + 13. Use with the GNU Affero General Public License. + + Notwithstanding any other provision of this License, you have +permission to link or combine any covered work with a work licensed +under version 3 of the GNU Affero General Public License into a single +combined work, and to convey the resulting work. The terms of this +License will continue to apply to the part which is the covered work, +but the special requirements of the GNU Affero General Public License, +section 13, concerning interaction through a network will apply to the +combination as such. + + 14. Revised Versions of this License. + + The Free Software Foundation may publish revised and/or new versions of +the GNU General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + + Each version is given a distinguishing version number. If the +Program specifies that a certain numbered version of the GNU General +Public License "or any later version" applies to it, you have the +option of following the terms and conditions either of that numbered +version or of any later version published by the Free Software +Foundation. If the Program does not specify a version number of the +GNU General Public License, you may choose any version ever published +by the Free Software Foundation. + + If the Program specifies that a proxy can decide which future +versions of the GNU General Public License can be used, that proxy's +public statement of acceptance of a version permanently authorizes you +to choose that version for the Program. + + Later license versions may give you additional or different +permissions. However, no additional obligations are imposed on any +author or copyright holder as a result of your choosing to follow a +later version. + + 15. Disclaimer of Warranty. + + THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY +APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT +HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY +OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, +THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM +IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF +ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. Limitation of Liability. + + IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS +THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY +GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE +USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF +DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD +PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), +EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF +SUCH DAMAGES. + + 17. Interpretation of Sections 15 and 16. + + If the disclaimer of warranty and limitation of liability provided +above cannot be given local legal effect according to their terms, +reviewing courts shall apply local law that most closely approximates +an absolute waiver of all civil liability in connection with the +Program, unless a warranty or assumption of liability accompanies a +copy of the Program in return for a fee. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Programs + + If you develop a new program, and you want it to be of the greatest +possible use to the public, the best way to achieve this is to make it +free software which everyone can redistribute and change under these terms. + + To do so, attach the following notices to the program. It is safest +to attach them to the start of each source file to most effectively +state the exclusion of warranty; and each file should have at least +the "copyright" line and a pointer to where the full notice is found. + + <one line to give the program's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. + +Also add information on how to contact you by electronic and paper mail. + + If the program does terminal interaction, make it output a short +notice like this when it starts in an interactive mode: + + <program> Copyright (C) <year> <name of author> + This program comes with ABSOLUTELY NO WARRANTY; for details type `show w'. + This is free software, and you are welcome to redistribute it + under certain conditions; type `show c' for details. + +The hypothetical commands `show w' and `show c' should show the appropriate +parts of the General Public License. Of course, your program's commands +might be different; for a GUI interface, you would use an "about box". + + You should also get your employer (if you work as a programmer) or school, +if any, to sign a "copyright disclaimer" for the program, if necessary. +For more information on this, and how to apply and follow the GNU GPL, see +<https://www.gnu.org/licenses/>. + + The GNU General Public License does not permit incorporating your program +into proprietary programs. If your program is a subroutine library, you +may consider it more useful to permit linking proprietary applications with +the library. If this is what you want to do, use the GNU Lesser General +Public License instead of this License. But first, please read +<https://www.gnu.org/licenses/why-not-lgpl.html>. diff --git a/examples/shellmath/README.md b/examples/shellmath/README.md new file mode 100644 index 0000000..1b47256 --- /dev/null +++ b/examples/shellmath/README.md @@ -0,0 +1,166 @@ +# Shellmath +Introducing decimal arithmetic libraries for the Bash shell, because +they said it couldn't be done... and because: + +. + + + +## Quick-start guide +Download this project and source the file `shellmath.sh` into your shell script, +then fire away at the shellmath API! + +The ___basic___ API looks like this: +``` + _shellmath_add arg1 arg2 [...] argN + _shellmath_subtract arg1 arg2 # means arg1 - arg2 + _shellmath_multiply arg1 arg2 [...] argN + _shellmath_divide arg1 arg2 # means arg1 / arg2 +``` + +The ___extended___ API introduces one more function: +``` + _shellmath_getReturnValue arg +``` + +This function optimizes away the need for ___$(___ subshelling ___)___ in order to capture `shellmath`'s output. +To use this feature, just be sure to set `__shellmath_isOptimized=1` at the top +of your script. (You can find an example in `faster_e_demo.sh`.) + +Operands to the _shellmath_ functions can be integers or decimal +numbers presented in either standard or scientific notation: +``` + _shellmath_add 1.009 4.223e-2 + _shellmath_getReturnValue sum + echo "The sum is $sum" +``` +Addition and multiplication are of arbitrary arity; try this on for size: +``` + _shellmath_multiply 1 2 3 4 5 6 + _shellmath_getReturnValue sixFactorial + echo "6 factorial is $sixFactorial" +``` +Subtraction and division, OTOH, are exclusively binary operations. + +## The demos +For a gentle introduction to `shellmath` run the demo `slower_e_demo.sh` +with a small whole-number argument, say 15: +``` +$ slower_e_demo.sh 15 +e = 2.7182818284589936 +``` + +This script uses a few `shellmath` API calls to calculate *e*, the mathematical +constant also known as [Euler's number](https://oeis.org/A001113). The argument +*15* tells the script to evaluate the *15th-degree* Maclaurin polynomial for *e*. +(That's the Taylor polynomial centered at 0.) Take a look inside the script to +see how it uses the `shellmath` APIs. + +There is another demo script very much like this one but *different*, and the +sensitive user can *feel* the difference. Try the following, but don't blink +or you'll miss it ;) +``` +$ faster_e_demo.sh 15 +e = 2.7182818284589936 +``` + +Did you feel the difference? Try the `-t` option with both scripts; this will produce +timing statistics. Here are my results +when running from my minGW64 command prompt on Windows 10 with an Intel i3 Core CPU: +``` +$ for n in {1..5}; do faster_e_demo.sh -t 15 2>&1; done | awk '/^real/ {print $2}' +0m0.055s +0m0.051s +0m0.056s +0m0.054s +0m0.054s + +$ for n in {1..5}; do slower_e_demo.sh -t 15 2>&1; done | awk '/^real/ {print $2}' +0m0.498s +0m0.594s +0m0.536s +0m0.511s +0m0.580s +``` + +(When sizing up these timings, do keep in mind that ___we are timing the +calculation of e from its Maclaurin polynomial. Every invocation of either +script is exercising the shellmath arithmetic subroutines 31 times.___) + +The comment header in `faster_e_demo.sh` explains the optimization and shows +how to put this faster version to work for you. + +## Runtime efficiency competitive with awk and bc +The file `timingData.txt` captures the results of some timing experiments that compare +`shellmath` against the GNU versions of the calculators `awk` and `bc`. The experiments +exercised each of the arithmetic operations and captured the results in a shell variable. +The result summary below shows that `shellmath` is competitive with `awk` and runs faster +than `bc` in these experiments. (One commenter noted that the differences in execution speed +can be partially explained by the fact that `shellmath` and `awk` use finite precision +whereas `bc` uses arbitrary precision. Another factor in these measurements is the need to +subshell 'awk' and 'bc' to capture their results, whereas 'shellmath' writes directly to +the shell's global memory.) + +Here are the run times of `shellmath` as a percentage of the `awk` and `bc` equivalents: +``` + versus awk versus bc + Addition: 82.2% 40.6% + Subtraction: 95.9% 50.5% + Multiplication: 135.9% 73.3% + Division: 80.3% 43.2% +``` + +Astute observers will note the experiments provide approximations to the sum, difference, +product, and quotient of *pi* and *e*. Unfortunately I did not gain insight as to which +of these values, if any, are +[transcendental](https://en.wikipedia.org/wiki/Transcendental_number#Possible_transcendental_numbers). + +You can find a deeper discussion of shellmath's runtime efficiency +[here](https://github.com/clarity20/shellmath/wiki/Shellmath-and-runtime-efficiency). + +## Background +The Bash shell does not have built-in operators for decimal arithmetic, making it +something of an oddity among well-known, widely-used programming languages. For the most part, +practitioners in need of powerful computational building blocks have naturally opted +for *other* languages and tools. Their widespread availability has diverted attention +from the possibility of *implementing* decimal arithmetic in Bash and it's easy to assume +that this ***cannot*** be done: + ++ From the indispensable _Bash FAQ_ (on _Greg's Wiki_): [How can I calculate with floating point numbers?](http://mywiki.wooledge.org/BashFAQ/022) + *"For most operations... an external program must be used."* ++ From Mendel Cooper's wonderful and encyclopedic _Advanced Bash Scripting Guide_: + [Bash does not understand floating point arithmetic. Use bc instead.](https://tldp.org/LDP/abs/html/ops.html#NOFLOATINGPOINT) ++ From a community discussion on Stack Overflow, _How do I use floating point division in bash?_ + The user's [preferred answer](https://stackoverflow.com/questions/12722095/how-do-i-use-floating-point-division-in-bash#12722107) + is a good example of _prevailing thought_ on this subject. + +Meanwhile, + ++ Bash maintainer (BDFL?) Chet Ramey sounds a (brighter?) note in [The Bash Reference Guide, Section 6.5](https://tiswww.case.edu/php/chet/bash/bashref.html#Shell-Arithmetic) + by emphasizing what the built-in arithmetic operators ***can*** do. + +But finally, a glimmer of hope: + ++ A [diamond-in-the-rough](http://stackoverflow.com/a/24431665/3776858) buried elsewhere + on Stack Overflow. + This down-and-dirty milestone computes the decimal quotient of two integer arguments. At a casual + glance, it seems to have drawn inspiration from the [Euclidean algorithm](https://mathworld.wolfram.com/EuclideanAlgorithm.html) + for computing GCDs, an entirely different approach than `shellmath`'s. + +Please try `shellmath` on for size and draw your own conclusions! + +## How it works +`shellmath` splits decimal numbers into their integer and fractional parts, +performs the appropriate integer operations on the parts, and recombines the results. +(In the spirit of Bash, numerical overflow is silently ignored.) + +Because if we can get carrying, borrowing, place value, and the distributive +law right, then the sky's the limit! As they say--erm, as they ___said___ in Rome, + + Ad astra per aspera. + +## And now... +You can run your floating-point calculations directly in Bash! + +## Please see also: +[A short discussion on arbitrary precision and shellmath](https://github.com/clarity20/shellmath/wiki/Shellmath-and-arbitrary-precision-arithmetic) diff --git a/examples/shellmath/assert.sh b/examples/shellmath/assert.sh new file mode 100644 index 0000000..bc4122e --- /dev/null +++ b/examples/shellmath/assert.sh @@ -0,0 +1,85 @@ +#!/bin/env bash +############################################################################### +# Internal test engine functions +############################################################################### + +RED='\033[0;31m' +GREEN='\033[0;32m' +NO_COLOR='\033[0m' + +function _shellmath_assert_returnCode() +{ + _shellmath_assert_functionReturn -c "$@" + return $? +} + +function _shellmath_assert_returnString() +{ + _shellmath_assert_functionReturn "$@" + return $? +} + +function _shellmath_assert_functionReturn() +{ + if [[ $# -lt 2 ]]; then + echo "USAGE: ${FUNCNAME[0]} [-c] returnStringOrCode functionName [ functionArgs ... ]" + echo " By default, asserts against the string output by the function." + echo " Use -c to assert against the numeric return code instead." + return "${__shellmath_returnCodes[FAIL]}" + fi + + if [[ "${1,,}" == '-c' ]]; then + mode=RETURN_CODE + shift + else + mode=RETURN_STRING + fi + + expectedReturn="$1" + func="$2" + shift 2 + + args=("$@") + + # Exercise the function in optimized mode; it will run faster by avoiding + # subshelling. This also suppresses dumping of function output to stdout. + __shellmath_isOptimized=${__shellmath_true} + "$func" "${args[@]}" + returnCode=$? + __shellmath_isOptimized=${__shellmath_false} + + # Fetch the return value(s) + local numReturnValues + declare -a actualReturn + _shellmath_getReturnValueCount numReturnValues + if ((numReturnValues == 1)); then + _shellmath_getReturnValue actualReturn[0] + else + # Multiple returns? Join them into one string + local _i evalString="_shellmath_getReturnValues" + for ((_i=0; _i<numReturnValues; _i++)); do + evalString+=" actualReturn[$_i]" + done + eval "$evalString" + fi + + if [[ $mode == RETURN_STRING ]]; then + if [[ "${actualReturn[*]}" == "$expectedReturn" ]]; then + _shellmath_setReturnValue "${GREEN}ok${NO_COLOR} " + return "$__shellmath_SUCCESS" + else + _shellmath_setReturnValue "${RED}FAIL${NO_COLOR} (${actualReturn[*]}) " + return "$__shellmath_FAIL" + fi + elif [[ $mode == RETURN_CODE ]]; then + if [[ "$returnCode" == "$expectedReturn" ]]; then + _shellmath_setReturnValue "${GREEN}ok${NO_COLOR} " + return "$__shellmath_SUCCESS" + else + _shellmath_setReturnValue "${RED}FAIL${NO_COLOR} ($returnCode) " + return "$__shellmath_FAIL" + fi + fi + +} + diff --git a/examples/shellmath/faster_e_demo.sh b/examples/shellmath/faster_e_demo.sh new file mode 100644 index 0000000..84558a2 --- /dev/null +++ b/examples/shellmath/faster_e_demo.sh @@ -0,0 +1,68 @@ +#!/usr/bin/env bash + +############################################################################### +# This script performs the same task as "slower_e_demo.sh" but with a major +# performance optimization. The speedup is especially noticeable on GNU +# emulation layers for Windows such as Cygwin and minGW, where the overhead +# of subshelling is quite significant. +# +# The speedup uses global storage space to simulate pass-and-return by +# reference so that you can capture the side effects of a function call without +# writing to stdout and wrapping the call in a subshell. How to use: +# +# Turn on "__shellmath_isOptimized" as shown below. +# Then instead of invoking "mySum = $(_shellmath_add $x $y)", +# call "_shellmath_add $x $y; _shellmath_getReturnValue mySum". +############################################################################### + +source shellmath.sh + +# Setting the '-t' flag will cause the script to time the algorithm +if [[ "$1" == '-t' ]]; then + do_timing=${__shellmath_true} + shift +fi + +if [[ $# -ne 1 ]]; then + echo "USAGE: ${BASH_SOURCE##*/} [-t] *N*" + echo " Approximates 'e' using the N-th order Maclaurin polynomial" + echo " (i.e. the Taylor polynomial centered at 0)." + echo " Specify the '-t' flag to time the main algorithm." + exit 0 +elif [[ ! "$1" =~ ^[0-9]+$ ]]; then + echo "Illegal argument. Whole numbers only, please." + exit 1 +fi + +__shellmath_isOptimized=${__shellmath_true} + + +function run_algorithm() +{ + # Initialize + n=0; N=$1; zero_factorial=1 + + # Initialize "e" to its zeroth-order term + _shellmath_divide 1 $zero_factorial + _shellmath_getReturnValue term + e=$term + + # Compute successive terms T(n) := T(n-1)/n and accumulate into e + for ((n=1; n<=N; n++)); do + _shellmath_divide "$term" "$n" + _shellmath_getReturnValue term + _shellmath_add "$e" "$term" + _shellmath_getReturnValue e + done + + echo "e = $e" +} + +if (( do_timing == __shellmath_true )); then + time run_algorithm "$1" +else + run_algorithm "$1" +fi + +exit 0 + diff --git a/examples/shellmath/image.png b/examples/shellmath/image.png Binary files differnew file mode 100644 index 0000000..4d3b898 --- /dev/null +++ b/examples/shellmath/image.png diff --git a/examples/shellmath/runTests.sh b/examples/shellmath/runTests.sh new file mode 100644 index 0000000..c9687e5 --- /dev/null +++ b/examples/shellmath/runTests.sh @@ -0,0 +1,124 @@ +#!/bin/env bash + +############################################################################### +# runTests.sh +# +# Usage: runTests.sh [testFile] +# where testFile defaults to testCases.in +# +# Processes a test file such as the testCases.in included with this package +############################################################################### + +# Process one line from the test cases file. Invoked below through mapfile. +function _shellmath_runTests() +{ + local lineNumber=$1 + local text=$2 + + # Trim leading whitespace + [[ $text =~ ^[$' \t']*(.*) ]] + text=${BASH_REMATCH[1]} + + # Skip comments and blank lines + [[ "$text" =~ ^# || -z $text ]] && return 0 + + # Check for line continuation + local len="${#text}" + if [[ ${text:$((len-1))} == '\' ]]; then + + # Eat the continuation character and add to the buffer + __shellfloat_commandBuffer+="${text/%\\/ }" + + # Defer processing + return + + # No line continuation + else + + # Assemble the command + local command=${__shellfloat_commandBuffer}${text} + __shellfloat_commandBuffer="" + + words=($command) + + # Expand first word to an assertion function + case ${words[0]} in + + Code) + words[0]=_shellmath_assert_return${words[0]} + + # Validate next word as a positive integer + if [[ ! "${words[1]}" =~ ^[0-9]+$ ]]; then + echo Line: "$lineNumber": Command "$command" + echo FAIL: \"Code\" requires integer return code + return 1 + else + nextWord=2 + fi + ;; + + String) + words[0]=_shellmath_assert_return${words[0]} + # Allow multiword arguments if quoted + if [[ ${words[1]} =~ ^\" ]]; then + if [[ ${words[1]} =~ \"$ ]]; then + nextWord=2 + else + for ((nextWord=2;;nextWord++)); do + if [[ ${words[nextWord]} =~ \"$ ]]; then + ((nextWord++)) + break + fi + done + fi + else + nextWord=2 + fi + ;; + + Both) + ;; + + *) + echo -e ${RED}FAIL${NO_COLOR} Line "$lineNumber": Command "$command": Code or String indicator required + return 2 + ;; + esac + + # Expand the next word to a shellmath function name + words[nextWord]=_shellmath_${words[nextWord]} + if ! type -t "${words[nextWord]}" >/dev/null; then + echo "${RED}FAIL${NO_COLOR} Line $lineNumber: Command "$command": Syntax error. Required: String|Code value operation args..." + return 3 + fi + + # Run the command, being respectful of shell metacharacters + fullCommand="${words[*]}" + eval "$fullCommand" + local returnString + _shellmath_getReturnValue returnString + echo -e "$returnString" Line "$lineNumber": "$command" + + fi + +} + + +function _main() +{ + source shellmath.sh + source assert.sh + + # Initialize certain globals. As "public" functions, the arithmetic + # functions need to do this themselves, but there are some "private" + # functions that need this here when they are auto-tested. + _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true + + # Process the test file line-by-line using the above runTests() function + mapfile -t -c 1 -C _shellmath_runTests -O 1 < "${1:-testCases.in}" + + exit 0 +} + +_main "$@" + diff --git a/examples/shellmath/shellmath.sh b/examples/shellmath/shellmath.sh new file mode 100644 index 0000000..5804ad2 --- /dev/null +++ b/examples/shellmath/shellmath.sh @@ -0,0 +1,1068 @@ +#!/bin/env bash +################################################################################ +# shellmath.sh +# Shell functions for floating-point arithmetic using only builtins +# +# Copyright (c) 2020 by Michael Wood. All rights reserved. +# +# Usage: +# +# source _thisPath_/_thisFileName_ +# +# # Conventional method: call the APIs by subshelling +# mySum=$( _shellmath_add 202.895 6.00311 ) +# echo $mySum +# +# # Optimized method: use hidden globals to simulate more flexible pass-and-return +# _shellmath_isOptimized=1 +# _shellmath_add 44.2 -87 +# _shellmath_getReturnValue mySum +# echo $mySum +# +################################################################################ + + +################################################################################ +# Program constants +################################################################################ +declare -A -r __shellmath_numericTypes=( + [INTEGER]=0 + [DECIMAL]=1 +) + +declare -A -r __shellmath_returnCodes=( + [SUCCESS]="0:Success" + [FAIL]="1:General failure" + [ILLEGAL_NUMBER]="2:Invalid argument; decimal number required: '%s'" + [DIVIDE_BY_ZERO]="3:Divide by zero error" +) + +declare -r -i __shellmath_true=1 +declare -r -i __shellmath_false=0 + +declare __shellmath_SUCCESS __shellmath_FAIL __shellmath_ILLEGAL_NUMBER + +################################################################################ +# Program state +################################################################################ +declare __shellmath_isOptimized=${__shellmath_false} +declare __shellmath_didPrecalc=${__shellmath_false} + + +################################################################################ +# Error-handling utilities +################################################################################ +function _shellmath_getReturnCode() +{ + local errorName=$1 + return "${__shellmath_returnCodes[$errorName]%%:*}" +} + +function _shellmath_warn() +{ + # Generate an error message and return control to the caller + _shellmath_handleError -r "$@" + return $? +} + +function _shellmath_exit() +{ + # Generate an error message and EXIT THE SCRIPT / interpreter + _shellmath_handleError "$@" +} + +function _shellmath_handleError() +{ + # Hidden option "-r" causes return instead of exit + local returnDontExit=$__shellmath_false + if [[ "$1" == "-r" ]]; then + returnDontExit=${__shellmath_true} + shift + fi + + # Format of $1: returnCode:msgTemplate + [[ "$1" =~ ^([0-9]+):(.*) ]] + returnCode=${BASH_REMATCH[1]} + msgTemplate=${BASH_REMATCH[2]} + shift + + # Display error msg, making parameter substitutions as needed + msgParameters="$*" + printf "$msgTemplate" "${msgParameters[@]}" + + if ((returnDontExit)); then + return "$returnCode" + else + exit "$returnCode" + fi +} + + +################################################################################ +# precalc() +# +# Pre-calculates certain global data and by setting the global variable +# "__shellmath_didPrecalc" records that this routine has been called. As an +# optimization, the caller should check that global to prevent needless +# invocations. +################################################################################ +function _shellmath_precalc() +{ + # Set a few global constants + _shellmath_getReturnCode SUCCESS; __shellmath_SUCCESS=$? + _shellmath_getReturnCode FAIL; __shellmath_FAIL=$? + _shellmath_getReturnCode ILLEGAL_NUMBER; __shellmath_ILLEGAL_NUMBER=$? + + # Determine the decimal precision to which we can accurately calculate. + # To do this we probe for the threshold at which integers overflow and + # take the integer floor of that number's base-10 logarithm. + # We check the 64-bit, 32-bit and 16-bit thresholds only. + if ((2**63 < 2**63-1)); then + __shellmath_precision=18 + __shellmath_maxValue=$((2**63-1)) + elif ((2**31 < 2**31-1)); then + __shellmath_precision=9 + __shellmath_maxValue=$((2**31-1)) + else ## ((2**15 < 2**15-1)) + __shellmath_precision=4 + __shellmath_maxValue=$((2**15-1)) + fi + + __shellmath_didPrecalc=$__shellmath_true +} + + +################################################################################ +# Simulate pass-and-return by reference using a secret global storage array +################################################################################ + +declare -a __shellmath_storage + +function _shellmath_setReturnValues() +{ + local -i _i + + for ((_i=1; _i<=$#; _i++)); do + __shellmath_storage[_i]="${!_i}" + done + + __shellmath_storage[0]=$# +} + +function _shellmath_getReturnValues() +{ + local -i _i + local evalString + + for ((_i=1; _i<=$#; _i++)); do + evalString+=${!_i}="${__shellmath_storage[_i]}"" " + done + + eval "$evalString" +} + +function _shellmath_setReturnValue() { __shellmath_storage=(1 "$1"); } +function _shellmath_getReturnValue() { eval "$1"=\"${__shellmath_storage[1]}\"; } +function _shellmath_getReturnValueCount() { eval "$1"=\"${__shellmath_storage[0]}\"; } + +################################################################################ +# validateAndParse(numericString) +# Return Code: SUCCESS or ILLEGAL_NUMBER +# Return Signature: integerPart fractionalPart isNegative numericType isScientific +# +# Validate and parse arguments to the main arithmetic routines +################################################################################ + +function _shellmath_validateAndParse() +{ + local n="$1" + local isNegative=${__shellmath_false} + local isScientific=${__shellmath_false} + local numericType returnCode + + ((returnCode = __shellmath_SUCCESS)) + + # Accept decimals: leading digits (optional), decimal point, trailing digits + if [[ "$n" =~ ^[-]?([0-9]*)\.([0-9]+)$ ]]; then + local integerPart=${BASH_REMATCH[1]:-0} + local fractionalPart=${BASH_REMATCH[2]} + + # Strip superfluous trailing zeros + if [[ "$fractionalPart" =~ ^(.*[^0])0*$ ]]; then + fractionalPart=${BASH_REMATCH[1]} + fi + + numericType=${__shellmath_numericTypes[DECIMAL]} + + # Factor out the negative sign if it is present + if [[ "$n" =~ ^- ]]; then + isNegative=${__shellmath_true} + n=${n:1} + fi + + _shellmath_setReturnValues "$integerPart" "$fractionalPart" \ + $isNegative "$numericType" $isScientific + return "$returnCode" + + # Accept integers + elif [[ "$n" =~ ^[-]?[0-9]+$ ]]; then + numericType=${__shellmath_numericTypes[INTEGER]} + + # Factor out the negative sign if it is present + if [[ "$n" =~ ^- ]]; then + isNegative=${__shellmath_true} + n=${n:1} + fi + + _shellmath_setReturnValues "$n" 0 $isNegative "$numericType" $isScientific + return "$returnCode" + + # Accept scientific notation: 1e5, 2.44E+10, etc. + elif [[ "$n" =~ (.*)[Ee](.*) ]]; then + local significand=${BASH_REMATCH[1]} + local exponent=${BASH_REMATCH[2]} + + # Validate the significand: optional sign, integer part, + # optional decimal point and fractional part + if [[ "$significand" =~ ^[-]?([0-9]+)(\.([0-9]+))?$ ]]; then + + isScientific=${__shellmath_true} + + # Separate the integer and fractional parts + local sigInteger=${BASH_REMATCH[1]} + local sigIntLength=${#sigInteger} + local sigFraction=${BASH_REMATCH[3]} + + # Strip superfluous trailing zeros + if [[ "$sigFraction" =~ ^(.*[^0])0*$ ]]; then + sigFraction=${BASH_REMATCH[1]} + fi + + local sigFracLength=${#sigFraction} + + if [[ "$n" =~ ^- ]]; then + isNegative=${__shellmath_true} + n=${n:1} + fi + + # Rewrite the scientifically-notated number in ordinary decimal notation. + # IOW, realign the integer and fractional parts. Separate with a space + # so they can be returned as two separate values + if ((exponent > 0)); then + local zeroCount integer fraction + ((zeroCount = exponent - sigFracLength)) + if ((zeroCount > 0)); then + printf -v zeros "%0*d" "$zeroCount" 0 + n=${sigInteger}${sigFraction}${zeros}" 0" + numericType=${__shellmath_numericTypes[INTEGER]} + elif ((zeroCount < 0)); then + n=${sigInteger}${sigFraction:0:exponent}" "${sigFraction:exponent} + numericType=${__shellmath_numericTypes[DECIMAL]} + else + n=${sigInteger}${sigFraction}" 0" + numericType=${__shellmath_numericTypes[INTEGER]} + fi + integer=${n% *}; fraction=${n#* } + _shellmath_setReturnValues "$integer" "$fraction" $isNegative "$numericType" $isScientific + return "$returnCode" + + elif ((exponent < 0)); then + local zeroCount integer fraction + ((zeroCount = -exponent - sigIntLength)) + if ((zeroCount > 0)); then + printf -v zeros "%0*d" "$zeroCount" 0 + n="0 "${zeros}${sigInteger}${sigFraction} + numericType=${__shellmath_numericTypes[DECIMAL]} + elif ((zeroCount < 0)); then + n=${sigInteger:0:-zeroCount}" "${sigInteger:(-zeroCount)}${sigFraction} + numericType=${__shellmath_numericTypes[DECIMAL]} + else + n="0 "${sigInteger}${sigFraction} + numericType=${__shellmath_numericTypes[DECIMAL]} + fi + integer=${n% *}; fraction=${n#* } + _shellmath_setReturnValues "$integer" "$fraction" $isNegative "$numericType" $isScientific + return "$returnCode" + + else + # exponent == 0 means the number is already aligned as desired + numericType=${__shellmath_numericTypes[DECIMAL]} + _shellmath_setReturnValues "$sigInteger" "$sigFraction" $isNegative "$numericType" $isScientific + return "$returnCode" + fi + + # Reject strings like xxx[Ee]yyy where xxx, yyy are not valid numbers + else + ((returnCode = __shellmath_ILLEGAL_NUMBER)) + _shellmath_setReturnValues "" + return "$returnCode" + fi + + # Reject everything else + else + ((returnCode = __shellmath_ILLEGAL_NUMBER)) + _shellmath_setReturnValues "" + return "$returnCode" + fi +} + + +################################################################################ +# numToScientific (integerPart, fractionalPart) +# +# Format conversion utility function +################################################################################ +function _shellmath_numToScientific() +{ + local integerPart=$1 fractionalPart=$2 + local exponent head tail scientific + + if ((integerPart > 0)); then + ((exponent = ${#integerPart}-1)) + head=${integerPart:0:1} + tail=${integerPart:1}${fractionalPart} + elif ((integerPart < 0)); then + ((exponent = ${#integerPart}-2)) # skip "-" and first digit + head=${integerPart:0:2} + tail=${integerPart:2}${fractionalPart} + else + [[ "$fractionalPart" =~ ^[-]?(0*)([^0])(.*)$ ]] + exponent=$((-(${#BASH_REMATCH[1]} + 1))) + head=${BASH_REMATCH[2]} + tail=${BASH_REMATCH[3]} + fi + + # Remove trailing zeros + [[ $tail =~ ^.*[^0] ]]; tail=${BASH_REMATCH[0]:-0} + + printf -v scientific "%d.%de%d" "$head" "$tail" "$exponent" + + _shellmath_setReturnValue "$scientific" +} + + +################################################################################ +# _shellmath_add (addend_1, addend_2) +################################################################################ +function _shellmath_add() +{ + local n1="$1" + local n2="$2" + + if ((! __shellmath_didPrecalc)); then + _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true + fi + + local isVerbose=$(( __shellmath_isOptimized == __shellmath_false )) + + # Is the caller itself an arithmetic function? + local isSubcall=${__shellmath_false} + local isMultiplication=${__shellmath_false} + if [[ "${FUNCNAME[1]}" =~ shellmath_(add|subtract|multiply|divide)$ ]]; then + isSubcall=${__shellmath_true} + if [[ "${BASH_REMATCH[1]}" == multiply ]]; then + isMultiplication=${__shellmath_true} + fi + fi + + # Handle corner cases where argument count is not 2 + local argCount=$# + if ((argCount == 0)); then + echo "Usage: ${FUNCNAME[0]} addend_1 addend_2" + return "$__shellmath_SUCCESS" + elif ((argCount == 1)); then + # Note the result as-is, print if running "normally", and return + _shellmath_setReturnValue "$n1" + (( isVerbose && ! isSubcall )) && echo "$n1" + return "$__shellmath_SUCCESS" + elif ((argCount > 2 && !isSubcall)); then + local recursiveReturn + + # Use a binary recursion tree to add everything up + # 1) left branch + _shellmath_add "${@:1:$((argCount/2))}"; recursiveReturn=$? + _shellmath_getReturnValue n1 + if (( recursiveReturn != __shellmath_SUCCESS )); then + _shellmath_setReturnValue "$n1" + return "$recursiveReturn" + fi + # 2) right branch + _shellmath_add "${@:$((argCount/2+1))}"; recursiveReturn=$? + _shellmath_getReturnValue n2 + if (( recursiveReturn != __shellmath_SUCCESS )); then + _shellmath_setReturnValue "$n2" + return "$recursiveReturn" + fi + # 3) head node + local sum + _shellmath_add "$n1" "$n2"; recursiveReturn=$? + _shellmath_getReturnValue sum + _shellmath_setReturnValue "$sum" + if (( isVerbose && ! isSubcall )); then + echo "$sum" + fi + return "$recursiveReturn" + fi + + local integerPart1 fractionalPart1 integerPart2 fractionalPart2 + local isNegative1 type1 isScientific1 isNegative2 type2 isScientific2 + local flags + + if ((isMultiplication)); then + integerPart1="$1" + fractionalPart1="$2" + integerPart2="$3" + fractionalPart2="$4" + + type1=${__shellmath_numericTypes[DECIMAL]} + type2=${__shellmath_numericTypes[DECIMAL]} + isNegative1=$__shellmath_false + isNegative2=$__shellmath_false + isScientific1=$__shellmath_false + isScientific2=$__shellmath_false + else + # Check and parse the arguments + _shellmath_validateAndParse "$n1"; flags=$? + _shellmath_getReturnValues integerPart1 fractionalPart1 isNegative1 type1 isScientific1 + if ((flags == __shellmath_ILLEGAL_NUMBER)); then + _shellmath_warn "${__shellmath_returnCodes[ILLEGAL_NUMBER]}" "$n1" + return $? + fi + _shellmath_validateAndParse "$n2"; flags=$? + _shellmath_getReturnValues integerPart2 fractionalPart2 isNegative2 type2 isScientific2 + if ((flags == __shellmath_ILLEGAL_NUMBER)); then + _shellmath_warn "${__shellmath_returnCodes[ILLEGAL_NUMBER]}" "$n2" + return $? + fi + fi + + # Quick add & return for integer adds + if ((type1==type2 && type1==__shellmath_numericTypes[INTEGER])); then + ((isNegative1)) && ((integerPart1*=-1)) + ((isNegative2)) && ((integerPart2*=-1)) + local sum=$((integerPart1 + integerPart2)) + if (( (!isSubcall) && (isScientific1 || isScientific2) )); then + _shellmath_numToScientific $sum "" + _shellmath_getReturnValue sum + fi + _shellmath_setReturnValue $sum + if (( isVerbose && ! isSubcall )); then + echo "$sum" + fi + return "$__shellmath_SUCCESS" + fi + + # Right-pad both fractional parts with zeros to the same length + local fractionalLen1=${#fractionalPart1} + local fractionalLen2=${#fractionalPart2} + if ((fractionalLen1 > fractionalLen2)); then + # Use printf to zero-pad. This avoids mathematical side effects. + printf -v fractionalPart2 %-*s "$fractionalLen1" "$fractionalPart2" + fractionalPart2=${fractionalPart2// /0} + elif ((fractionalLen2 > fractionalLen1)); then + printf -v fractionalPart1 %-*s "$fractionalLen2" "$fractionalPart1" + fractionalPart1=${fractionalPart1// /0} + fi + local unsignedFracLength=${#fractionalPart1} + + # Implement a sign convention that will enable us to detect carries by + # comparing string lengths of addends and sums: propagate the sign across + # both numeric parts (whether unsigned or zero). + if ((isNegative1)); then + fractionalPart1="-"$fractionalPart1 + integerPart1="-"$integerPart1 + fi + if ((isNegative2)); then + fractionalPart2="-"$fractionalPart2 + integerPart2="-"$integerPart2 + fi + + local integerSum=0 + local fractionalSum=0 + + ((integerSum = integerPart1+integerPart2)) + + # Summing the fractional parts is tricky: We need to override the shell's + # default interpretation of leading zeros, but the operator for doing this + # (the "10#" operator) cannot work directly with negative numbers. So we + # break it all down. + if ((isNegative1)); then + ((fractionalSum += (-1) * 10#${fractionalPart1:1})) + else + ((fractionalSum += 10#$fractionalPart1)) + fi + if ((isNegative2)); then + ((fractionalSum += (-1) * 10#${fractionalPart2:1})) + else + ((fractionalSum += 10#$fractionalPart2)) + fi + + unsignedFracSumLength=${#fractionalSum} + if [[ "$fractionalSum" =~ ^[-] ]]; then + ((unsignedFracSumLength--)) + fi + + # Restore any leading zeroes that were lost when adding + if ((unsignedFracSumLength < unsignedFracLength)); then + local lengthDiff=$((unsignedFracLength - unsignedFracSumLength)) + local zeroPrefix + printf -v zeroPrefix "%0*d" "$lengthDiff" 0 + if ((fractionalSum < 0)); then + fractionalSum="-"${zeroPrefix}${fractionalSum:1} + else + fractionalSum=${zeroPrefix}${fractionalSum} + fi + fi + + # Carry a digit from fraction to integer if required + if ((10#$fractionalSum!=0 && unsignedFracSumLength > unsignedFracLength)); then + local carryAmount + ((carryAmount = isNegative1?-1:1)) + ((integerSum += carryAmount)) + # Remove the leading 1-digit whether the fraction is + or - + fractionalSum=${fractionalSum/1/} + fi + + # Transform the partial sums from additive to concatenative. Example: the + # pair (-2,3) is not -2.3 but rather (-2)+(0.3), i.e. -1.7 so we want to + # transform (-2,3) to (-1,7). This transformation is meaningful when + # the two parts have opposite signs, so that's what we look for. + if ((integerSum < 0 && 10#$fractionalSum > 0)); then + ((integerSum += 1)) + ((fractionalSum = 10#$fractionalSum - 10**unsignedFracSumLength)) + elif ((integerSum > 0 && 10#$fractionalSum < 0)); then + ((integerSum -= 1)) + ((fractionalSum = 10**unsignedFracSumLength + 10#$fractionalSum)) + fi + # This last case needs to function either as an "else" for the above, + # or as a coda to the "if" clause when integerSum is -1 initially. + if ((integerSum == 0 && 10#$fractionalSum < 0)); then + integerSum="-"$integerSum + ((fractionalSum *= -1)) + fi + + # Touch up the numbers for display + local sum + ((10#$fractionalSum < 0)) && fractionalSum=${fractionalSum:1} + if (( (!isSubcall) && (isScientific1 || isScientific2) )); then + _shellmath_numToScientific "$integerSum" "$fractionalSum" + _shellmath_getReturnValue sum + elif ((10#$fractionalSum)); then + printf -v sum "%s.%s" "$integerSum" "$fractionalSum" + else + sum=$integerSum + fi + + # Note the result, print if running "normally", and return + _shellmath_setReturnValue $sum + if (( isVerbose && ! isSubcall )); then + echo "$sum" + fi + + return "$__shellmath_SUCCESS" +} + + +################################################################################ +# subtract (subtrahend, minuend) +################################################################################ +function _shellmath_subtract() +{ + local n1="$1" + local n2="$2" + local isVerbose=$(( __shellmath_isOptimized == __shellmath_false )) + + if ((! __shellmath_didPrecalc)); then + _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true + fi + + if (( $# == 0 || $# > 2 )); then + echo "Usage: ${FUNCNAME[0]} subtrahend minuend" + return "$__shellmath_SUCCESS" + elif (( $# == 1 )); then + # Note the value as-is and return + _shellmath_setReturnValue "$n1" + ((isVerbose)) && echo "$n1" + return "$__shellmath_SUCCESS" + fi + + # Symbolically negate the second argument + if [[ "$n2" =~ ^- ]]; then + n2=${n2:1} + else + n2="-"$n2 + fi + + # Calculate, note the result, print if running "normally", and return + local difference + _shellmath_add "$n1" "$n2" + _shellmath_getReturnValue difference + if ((isVerbose)); then + echo "$difference" + fi + + return $? +} + + +################################################################################ +# reduceOuterPairs (two integer parts [, two fractional parts]) +# +# Examines the magnitudes of two numbers in advance of a multiplication +# and either chops off their lowest-order digits or pushes them to the +# corresponding lower-order parts in order to prevent overflow in the product. +# The choice depends on whether 2 or 4 arguments are supplied. +################################################################################ +function _shellmath_reduceOuterPairs() +{ + local value1="$1" value2="$2" subvalue1="$3" subvalue2="$4" + + local digitExcess value1Len=${#value1} value2Len=${#value2} + ((digitExcess = value1Len + value2Len - __shellmath_precision)) + + # Be very precise about detecting overflow. The "digit excess" underestimates + # this: floor(log_10(longLongMax)). We don't want to needlessly lose precision + # when a product barely squeezes under the exact threshold. + if ((digitExcess>1 || (digitExcess==1 && value1 > __shellmath_maxValue/value2) )); then + + # Identify the digit-tails to be pruned off and either discarded or + # pushed past the decimal point. In pruning the two values we want to + # retain as much "significance" as possible, so we try to equalize the + # lengths of the remaining digit sequences. + local tail1 tail2 + local lengthDiff leftOver + + # Which digit string is longer, and by how much? + ((lengthDiff = value1Len - value2Len)) + if ((lengthDiff > 0)); then + if ((digitExcess <= lengthDiff)); then + # Chop digits from the longer string only + tail1=${value1:(-digitExcess)} + tail2="" # do not chop anything + else + # Chop more digits from the longer string so the two strings + # end up as nearly-equal in length as possible + ((leftOver = digitExcess - lengthDiff)) + tail1=${value1:(-(lengthDiff + leftOver/2))} + tail2=${value2:(-((leftOver+1)/2))} + fi + else + ((lengthDiff *= -1)) + # Mirror the above code block but swap 1 and 2 + if ((digitExcess <= lengthDiff)); then + tail1="" + tail2=${value2:(-digitExcess)} + else + ((leftOver = digitExcess - lengthDiff)) + tail1=${value1:(-((leftOver+1)/2))} + tail2=${value2:(-(lengthDiff + leftOver/2))} + fi + fi + + # Discard the least-significant digits or move them past the decimal point + value1=${value1%${tail1}} + [[ -n "$subvalue1" ]] && subvalue1=${tail1}${subvalue1%0} # remove placeholder zero + value2=${value2%${tail2}} + [[ -n "$subvalue2" ]] && subvalue2=${tail2}${subvalue2%0} + else + # Signal the caller that no rescaling was actually done + ((digitExcess = 0)) + fi + + _shellmath_setReturnValues "$value1" "$value2" \ + "$subvalue1" "$subvalue2" "$digitExcess" +} + +################################################################################ +# rescaleValue(value, rescaleFactor) +# +# Upscales a decimal value by "factor" orders of magnitude: 3.14159 --> 3141.59 +################################################################################ +function _shellmath_rescaleValue() +{ + local value="$1" rescalingFactor="$2" + local head tail zeroCount zeroTail + + [[ "$value" =~ ^(.*)\.(.*)$ ]] + head=${BASH_REMATCH[1]} + tail=${BASH_REMATCH[2]} + ((zeroCount = rescalingFactor - ${#tail})) + if ((zeroCount > 0)); then + printf -v zeroTail "%0*d" "$zeroCount" 0 + value=${head}${tail}${zeroTail} + elif ((zeroCount < 0)); then + value=${head}${tail:0:rescalingFactor}"."${tail:rescalingFactor} + else + value=${head}${tail} + fi + + _shellmath_setReturnValue "$value" +} + +################################################################################ +# reduceCrossPairs (two integer parts, two fractional parts) +# +# Examines the precision of the inner products (of "multiplication by parts") +# and if necessary truncates the fractional part(s) to prevent overflow +################################################################################ +function _shellmath_reduceCrossPairs() +{ + local value1="$1" value2="$2" subvalue1="$3" subvalue2="$4" + + local digitExcess value1Len=${#value1} value2Len=${#value2} + local subvalue1Len=${#subvalue1} subvalue2Len=${#subvalue2} + + # Check BOTH cross-products + ((digitExcess = value1Len + subvalue2Len - __shellmath_precision)) + if ((digitExcess > 1 || (digitExcess==1 && value1 > __shellmath_maxValue/subvalue2) )); then + subvalue2=${subvalue2:0:(-digitExcess)} + fi + ((digitExcess = value2Len + subvalue1Len - __shellmath_precision)) + if ((digitExcess > 1 || (digitExcess==1 && value2 > __shellmath_maxValue/subvalue1) )); then + subvalue1=${subvalue1:0:(-digitExcess)} + fi + + _shellmath_setReturnValues "$subvalue1" "$subvalue2" +} + + +function _shellmath_round() +{ + local number="$1" digitCount="$2" + local nextDigit=${number:digitCount:1} + + number=${number:0:digitCount} + if ((nextDigit >= 5)); then + printf -v number "%0*d" "$digitCount" $((10#$number + 1)) + fi + + _shellmath_setReturnValue "$number" +} + +################################################################################ +# multiply (multiplicand, multiplier) +################################################################################ +function _shellmath_multiply() +{ + local n1="$1" + local n2="$2" + + if ((! __shellmath_didPrecalc)); then + _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true + fi + + local isVerbose=$(( __shellmath_isOptimized == __shellmath_false )) + + # Is the caller itself an arithmetic function? + local isSubcall=${__shellmath_false} + if [[ "${FUNCNAME[1]}" =~ shellmath_(add|subtract|multiply|divide)$ ]]; then + isSubcall=${__shellmath_true} + fi + + # Handle corner cases where argument count is not 2 + local argCount=$# + if ((argCount == 0)); then + echo "Usage: ${FUNCNAME[0]} factor_1 factor_2" + return "$__shellmath_SUCCESS" + elif ((argCount == 1)); then + # Note the value as-is and return + _shellmath_setReturnValue "$n1" + (( isVerbose && ! isSubcall )) && echo "$n1" + return "$__shellmath_SUCCESS" + elif ((argCount > 2)); then + local recursiveReturn + + # Use a binary recursion tree to multiply everything out + # 1) left branch + _shellmath_multiply "${@:1:$((argCount/2))}"; recursiveReturn=$? + _shellmath_getReturnValue n1 + if (( recursiveReturn != __shellmath_SUCCESS )); then + _shellmath_setReturnValue "$n1" + return "$recursiveReturn" + fi + # 2) right branch + _shellmath_multiply "${@:$((argCount/2+1))}"; recursiveReturn=$? + _shellmath_getReturnValue n2 + if (( recursiveReturn != __shellmath_SUCCESS )); then + _shellmath_setReturnValue "$n2" + return "$recursiveReturn" + fi + # 3) head node + local product + _shellmath_multiply "$n1" "$n2"; recursiveReturn=$? + _shellmath_getReturnValue product + _shellmath_setReturnValue "$product" + if (( isVerbose && ! isSubcall )); then + echo "$product" + fi + return "$recursiveReturn" + fi + + local integerPart1 fractionalPart1 integerPart2 fractionalPart2 + local isNegative1 type1 isScientific1 isNegative2 type2 isScientific2 + local flags + + # Check and parse the arguments + _shellmath_validateAndParse "$n1"; flags=$? + _shellmath_getReturnValues integerPart1 fractionalPart1 isNegative1 type1 isScientific1 + if ((flags == __shellmath_ILLEGAL_NUMBER)); then + _shellmath_warn "${__shellmath_returnCodes[ILLEGAL_NUMBER]}" "$n1" + return $? + fi + _shellmath_validateAndParse "$n2"; flags=$? + _shellmath_getReturnValues integerPart2 fractionalPart2 isNegative2 type2 isScientific2 + if ((flags == __shellmath_ILLEGAL_NUMBER)); then + _shellmath_warn "${__shellmath_returnCodes[ILLEGAL_NUMBER]}" "$n2" + return $? + fi + + # Overflow / underflow detection and accommodation + local rescalingFactor=0 + if ((${#integerPart1} + ${#integerPart2} + ${#fractionalPart1} + ${#fractionalPart2} >= ${__shellmath_precision})); then + _shellmath_reduceOuterPairs "$integerPart1" "$integerPart2" "$fractionalPart1" "$fractionalPart2" + _shellmath_getReturnValues integerPart1 integerPart2 fractionalPart1 fractionalPart2 rescalingFactor + if ((10#$fractionalPart1)); then type1=${__shellmath_numericTypes[DECIMAL]}; fi + if ((10#$fractionalPart2)); then type2=${__shellmath_numericTypes[DECIMAL]}; fi + + _shellmath_reduceCrossPairs "$integerPart1" "$integerPart2" "$fractionalPart1" "$fractionalPart2" + _shellmath_getReturnValues fractionalPart1 fractionalPart2 + + _shellmath_reduceOuterPairs "$fractionalPart1" "$fractionalPart2" + _shellmath_getReturnValues fractionalPart1 fractionalPart2 + fi + + # Quick multiply & return for integer multiplies + if ((type1==type2 && type1==__shellmath_numericTypes[INTEGER])); then + ((isNegative1)) && ((integerPart1*=-1)) + ((isNegative2)) && ((integerPart2*=-1)) + local product=$((integerPart1 * integerPart2)) + if ((rescalingFactor > 0)); then + _shellmath_rescaleValue "$product" "$rescalingFactor" + _shellmath_getReturnValue product + fi + if (( (!isSubcall) && (isScientific1 || isScientific2) )); then + _shellmath_numToScientific $product "" + _shellmath_getReturnValue product + fi + _shellmath_setReturnValue $product + if (( isVerbose && ! isSubcall )); then + echo "$product" + fi + return "$__shellmath_SUCCESS" + fi + + # The product has four components per the distributive law + local intProduct floatProduct innerProduct1 innerProduct2 + # Widths of the decimal parts + local floatWidth fractionalWidth1 fractionalWidth2 + + # Compute the integer and floating-point components + ((intProduct = integerPart1 * integerPart2)) + + fractionalWidth1=${#fractionalPart1} + fractionalWidth2=${#fractionalPart2} + ((floatWidth = fractionalWidth1 + fractionalWidth2)) + ((floatProduct = 10#$fractionalPart1 * 10#$fractionalPart2)) + if ((${#floatProduct} < floatWidth)); then + printf -v floatProduct "%0*d" "$floatWidth" "$floatProduct" + fi + + # Compute the inner products: First integer-multiply, then rescale + ((innerProduct1 = integerPart1 * 10#$fractionalPart2)) + ((innerProduct2 = integerPart2 * 10#$fractionalPart1)) + + # Rescale the inner products back to decimals so we can shellmath_add() them + if ((fractionalWidth2 <= ${#innerProduct1})); then + local innerInt1=${innerProduct1:0:(-$fractionalWidth2)} + local innerFloat1=${innerProduct1:(-$fractionalWidth2)} + integerPart1=${innerInt1} + fractionalPart1=${innerFloat1} + else + integerPart1=0 + printf -v fractionalPart1 "%0*d" "$fractionalWidth2" "$innerProduct1" + fi + if ((fractionalWidth1 <= ${#innerProduct2})); then + local innerInt2=${innerProduct2:0:(-$fractionalWidth1)} + local innerFloat2=${innerProduct2:(-$fractionalWidth1)} + integerPart2=${innerInt2} + fractionalPart2=${innerFloat2} + else + integerPart2=0 + printf -v fractionalPart2 "%0*d" "$fractionalWidth1" "$innerProduct2" + fi + + # Combine the distributed parts + local innerSum product + # Add the inner products to get the inner sum + _shellmath_add "$integerPart1" "$fractionalPart1" "$integerPart2" "$fractionalPart2" + _shellmath_getReturnValue innerSum + [[ "$innerSum" =~ (.*)\.(.*) ]] + integerPart1=${BASH_REMATCH[1]} + fractionalPart1=${BASH_REMATCH[2]} + # Add inner sum + outer sum + _shellmath_add "$integerPart1" "$fractionalPart1" "$intProduct" "$floatProduct" + _shellmath_getReturnValue product + + # Determine the sign of the product + if ((isNegative1 != isNegative2)); then + product="-"$product + fi + + # When we pre-detect overflow in the integer part of the computation, + # we compensate by shrinking the inputs by some order of magnitude. + # Having now finished the computation, we revert to the original magnitude. + if ((rescalingFactor > 0)); then + _shellmath_rescaleValue "$product" "$rescalingFactor" + _shellmath_getReturnValue product + fi + + # Convert to scientific notation if appropriate + if (( (!isSubcall) && (isScientific1 || isScientific2) )); then + _shellmath_numToScientific "${product%.*}" "${product#*.}" + _shellmath_getReturnValue product + fi + + # Note the result, print if running "normally", and return + _shellmath_setReturnValue $product + if (( isVerbose && ! isSubcall )); then + echo "$product" + fi + + return "$__shellmath_SUCCESS" +} + + +################################################################################ +# divide (dividend, divisor) +################################################################################ +function _shellmath_divide() +{ + local n1="$1" + local n2="$2" + local integerPart1 fractionalPart1 integerPart2 fractionalPart2 + local isNegative1 type1 isScientific1 isNegative2 type2 isScientific2 + + if ((! __shellmath_didPrecalc)); then + _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true + fi + + local isVerbose=$(( __shellmath_isOptimized == __shellmath_false )) + + local isTesting=${__shellmath_false} + if [[ "${FUNCNAME[1]}" == "_shellmath_assert_functionReturn" ]]; then + isTesting=${__shellmath_true} + fi + + if [[ $# -eq 0 || $# -gt 2 ]]; then + echo "Usage: ${FUNCNAME[0]} dividend divisor" + return "$__shellmath_SUCCESS" + elif [[ $# -eq 1 ]]; then + # Note the value as-is and return + _shellmath_setReturnValue "$n1" + ((isVerbose)) && echo "$n1" + return "$__shellmath_SUCCESS" + fi + + # Check and parse the arguments + local flags + _shellmath_validateAndParse "$n1"; flags=$? + _shellmath_getReturnValues integerPart1 fractionalPart1 isNegative1 type1 isScientific1 + if ((flags == __shellmath_ILLEGAL_NUMBER)); then + _shellmath_warn "${__shellmath_returnCodes[ILLEGAL_NUMBER]}" "$n1" + return $? + fi + _shellmath_validateAndParse "$n2"; flags=$? + _shellmath_getReturnValues integerPart2 fractionalPart2 isNegative2 type2 isScientific2 + if ((flags == __shellmath_ILLEGAL_NUMBER)); then + _shellmath_warn "${__shellmath_returnCodes[ILLEGAL_NUMBER]}" "$n2" + return $? + fi + + # Throw error on divide by zero + if ((integerPart2 == 0 && 10#$fractionalPart2 == 0)); then + _shellmath_warn "${__shellmath_returnCodes[DIVIDE_BY_ZERO]}" "$n2" + return $? + fi + + # Convert the division problem to an *integer* division problem by rescaling + # both inputs so as to lose their decimal points. To obtain maximal precision, + # we scale up the numerator further, padding with as many zeros as it can hold + local numerator denominator quotient + local rescaleFactor zeroCount zeroTail + + if ((integerPart1 == 0)); then + integerPart1="" + fi + ((zeroCount = __shellmath_precision - ${#integerPart1} - ${#fractionalPart1})) + ((rescaleFactor = __shellmath_precision - ${#integerPart1} - ${#fractionalPart2})) + if ((zeroCount > 0)); then + printf -v zeroTail "%0*d" "$zeroCount" 0 + fi + + # Rescale and rewrite the fraction to be computed, and compute it + numerator=${integerPart1}${fractionalPart1}${zeroTail} + denominator=${integerPart2}${fractionalPart2} + ((quotient = 10#$numerator / 10#$denominator)) + + # For greater precision, re-divide by the remainder to get the next digits of the quotient + local remainder quotient_2 + ((remainder = 10#$numerator % 10#$denominator)) # cannot exceed numerator or thus, maxValue + ((zeroCount = __shellmath_precision - ${#remainder})) + if ((zeroCount > 0)); then + printf -v zeroTail "%0*d" "$zeroCount" 0 + else + zeroTail="" + fi + # Derive the new numerator from the remainder. Do not change the denominator. + numerator=${remainder}${zeroTail} + ((quotient_2 = 10#$numerator / 10#$denominator)) + quotient=${quotient}${quotient_2} + ((rescaleFactor += ${#quotient_2})) + + # Rescale back. For aesthetic reasons we also round off at the "precision"th decimal place + ((zeroCount = rescaleFactor - ${#quotient})) + if ((zeroCount >= 0)); then + local zeroPrefix="" fractionalPart + if ((zeroCount > 0)); then + printf -v zeroPrefix "%0*d" "$((rescaleFactor - ${#quotient}))" 0 + fi + fractionalPart=${zeroPrefix}${quotient} + _shellmath_round "$fractionalPart" $__shellmath_precision + _shellmath_getReturnValue fractionalPart + quotient="0."${fractionalPart} + else + fractionalPart=${quotient:(-$rescaleFactor)} + _shellmath_round "$fractionalPart" $__shellmath_precision + _shellmath_getReturnValue fractionalPart + quotient=${quotient:0:(-$rescaleFactor)}"."${fractionalPart} + fi + + # Determine the sign of the quotient + if ((isNegative1 != isNegative2)); then + quotient="-"$quotient + fi + + if ((isTesting)); then + # Trim zeros. (Requires decimal point and zero tail.) + if [[ "$quotient" =~ [\.].*0$ ]]; then + # If the decimal point IMMEDIATELY precedes the 0s, remove that too + [[ $quotient =~ [\.]?0+$ ]] + quotient=${quotient%${BASH_REMATCH[0]}} + fi + fi + + # Convert to scientific notation if appropriate + if ((isScientific1 || isScientific2)); then + _shellmath_numToScientific "${quotient%.*}" "${quotient#*.}" + _shellmath_getReturnValue quotient + fi + + # Note the result, print if running "normally", and return + _shellmath_setReturnValue "$quotient" + if ((isVerbose)); then + echo "$quotient" + fi + + return "$__shellmath_SUCCESS" +} + diff --git a/examples/shellmath/slower_e_demo.sh b/examples/shellmath/slower_e_demo.sh new file mode 100644 index 0000000..d8fc931 --- /dev/null +++ b/examples/shellmath/slower_e_demo.sh @@ -0,0 +1,55 @@ +#!/usr/bin/env bash + +############################################################################### +# This script illustrates the use of the shellmath APIs to perform +# decimal calculations. Here we approximate the mathematical constant 'e' +# using its Maclaurin polynomials (i.e. its Taylor polynomials centered at 0). +############################################################################### + +source shellmath.sh + +# Setting the '-t' flag will cause the script to time the algorithm +if [[ "$1" == '-t' ]]; then + do_timing=${__shellmath_true} + shift +fi + +if [[ $# -ne 1 ]]; then + echo "USAGE: ${BASH_SOURCE##*/} [-t] *N*" + echo " Approximates 'e' using the N-th order Maclaurin polynomial" + echo " (i.e. the Taylor polynomial centered at 0)." + echo " Specify the '-t' flag to time the main algorithm." + exit 0 +elif [[ ! "$1" =~ ^[0-9]+$ ]]; then + echo "Illegal argument. Whole numbers only, please." + exit 1 +fi + + +function run_algorithm() +{ + # Initialize + n=0; N=$1; zero_factorial=1 + + # Initialize e to the zeroth-order term + term=$(_shellmath_divide 1 $zero_factorial) + e=$term + + # Compute successive terms T(n) := T(n-1)/n and accumulate into e + for ((n=1; n<=N; n++)); do + term=$(_shellmath_divide "$term" "$n") + e=$(_shellmath_add "$e" "$term") + done + + echo "e = $e" +} + + +if (( do_timing == __shellmath_true )); then + time run_algorithm "$1" +else + run_algorithm "$1" +fi + +exit 0 + diff --git a/examples/shellmath/testCases.in b/examples/shellmath/testCases.in new file mode 100644 index 0000000..54e3a82 --- /dev/null +++ b/examples/shellmath/testCases.in @@ -0,0 +1,142 @@ +################################################################ +# The general testcase syntax is +# assertionType expectedValue functionUnderTest [args ... ] +# +# where assertionType is either of: +# Code to indicate the (bash-style) integer return code +# String to indicate the string "printed" as a side effect +# +# and functionUnderTest is the function name +# with the "_shellmath_" prefix removed. +################################################################ + +################################ +# Tests for SUPPORTING FUNCTIONS +################################ + +# Tests for getReturnCode() +Code 0 getReturnCode SUCCESS +Code 1 getReturnCode FAIL +Code 2 getReturnCode ILLEGAL_NUMBER + +## Tests for validateAndParse(): +## Validate a number, determine its type and sign, split it into parts + +# Detect Invalid input +Code 2 validateAndParse NaN +String "" validateAndParse NaN +# Positive integers +String "4 0 0 0 0" validateAndParse 4 +# Negative integers +String "9 0 1 0 0" validateAndParse -9 +# Decimals +String "4 2 0 1 0" validateAndParse 4.2 +# Negative decimals +String "4 2 1 1 0" validateAndParse -4.2 +# Scientific / exponential notation: Check all code branches +String "340000 0 0 0 1" validateAndParse 3.4e5 +String "344 4 0 1 1" validateAndParse 3.444e2 +String "34567 0 0 0 1" validateAndParse 3.4567e4 +String "0 003456 0 1 1" validateAndParse 3.456e-3 +String "34 56 0 1 1" validateAndParse 345.6e-1 +String "0 23011 0 1 1" validateAndParse 23.011e-2 +String "23 011 0 1 1" validateAndParse 23.011e0 + +#################### +# Tests for ADDITION +#################### +String 4 add 4 +String 9 add 4 5 + +# Same-length decimal tails with no leading zeros, no carry across decimal point +String 2.214 add 1.105 1.109 + +# Carry across decimal point +String 3.8 add 1.9 1.9 +String -3.8 add -1.9 -1.9 + +# Different-length decimals, one with leading zero +String 2.195 add 1.105 1.09 +String -2.195 add -1.105 -1.09 + +# Same-length tails having leading zeros +String 2.014 add 1.005 1.009 +String -2.014 add -1.005 -1.009 +# Different-length tails with and without leading zeros +String 3.31462 add 1.905 1.40962 +String 2.01462 add 1.005 1.00962 + +# Subtraction +String 2.5 subtract 5.2 2.7 +String -2.5 subtract 2.7 5.2 +String 2.5 add 5.2 -2.7 + +# Integer part equal to 0 +String 1.5 add 0.6 0.9 +String 1.5 add .6 .9 +String -0.3 add 0.6 -0.9 +String -0.3 add .6 -.9 + +# Recursive/multiple addition +String 12 add 2 4 6 +String 6.6 add 1.1 2.2 3.3 + +########################## +# Tests for MULTIPLICATION +########################## +String 4 multiply 4 +String 20 multiply 4 5 + +String 21.32 multiply 4.1 5.2 +String -21.32 multiply -4.1 5.2 + +# Carry-heavy products +String 98.901 multiply 9.9 9.99 + +# Leading zeros after decimal point: +# Track place value with zero-padding +String 1.0201 multiply 1.01 1.01 +String 0.0001 multiply 0.01 0.01 +String 0.0001 add 0 0.0001 + +# Staggered decimal precisions +String 0.000001 multiply 0.01 0.0001 + +# Interpret in base 10 +String 2.2781 multiply 1.09 2.09 + +# Recursive multiplication +String 35.1384 multiply 1.1 2.2 3.3 4.4 + +#################### +# Tests for DIVISION +#################### +String 4 divide 4 +String 4 divide 20 5 + +String 0.5 divide 1 2 +String -0.5 divide -1 2 + +# Mixed fractions +String 34.54 divide 3454 100 + +# Non-terminating decimals +String 0.166666666666666667 divide 1 6 + +# Decimal arguments +String 0.25 divide 0.5 2 +String 0.04165 divide 0.1666 4 + +########################### +# Tests for scientific math +########################### +String 8.8e4 add 1.1e4 7.7e4 +String 4.239e1 add 1.224e1 3.015e1 +String -6.6e4 add 1.1e4 -7.7e4 +String -66000 add 11000 -77000 +String 1.23123e2 add 1.23e2 1.23e-1 +String 8.1403e7 multiply 2.03e5 4.01e2 +String 1.0e-7 multiply 1.0e-3 1.0e-4 +String 1.0e-7 multiply 1e-3 1e-4 + + diff --git a/examples/shellmath/timingData.txt b/examples/shellmath/timingData.txt new file mode 100644 index 0000000..d1de887 --- /dev/null +++ b/examples/shellmath/timingData.txt @@ -0,0 +1,42 @@ +$ ######## Activate optimized mode as described in the README ######## +$ __shellmath_isOptimized=1 + +$ ######## Addition ######## +$ time { for ((i=0; i<100; i++)); do _shellmath_add 3.1415926 2.7182818; _shellmath_getReturnValue sum; done; } +real 0m0.196s +user 0m0.195s +sys 0m0.000s +$ time { for ((i=0; i<100; i++)); do sum=$(bc <<< "3.1415926+2.7182818"); done; } +real 0m0.488s +user 0m0.092s +sys 0m0.384s + +$ ######## Subtraction ######## +$ time { for ((i=0; i<100; i++)); do _shellmath_subtract 3.1415926 2.7182818; _shellmath_getReturnValue diff; done; } +real 0m0.236s +user 0m0.234s +sys 0m0.001s +$ time { for ((i=0; i<100; i++)); do diff=$(bc <<< "3.1415926-2.7182818"); done; } +real 0m0.461s +user 0m0.090s +sys 0m0.388s + +$ ######## Multiplication ######## +$ time { for ((i=0; i<100; i++)); do _shellmath_multiply 3.1415926 2.7182818; _shellmath_getReturnValue prod; done; } +real 0m0.340s +user 0m0.333s +sys 0m0.005s +$ time { for ((i=0; i<100; i++)); do prod=$(bc <<< "3.1415926*2.7182818"); done; } +real 0m0.465s +user 0m0.105s +sys 0m0.377s + +$ ######## Division ######## +$ time { for ((i=0; i<100; i++)); do _shellmath_divide 3.1415926/2.7182818; _shellmath_getReturnValue quot; done; } +real 0m0.196s +user 0m0.195s +sys 0m0.000s +$ time { for ((i=0; i<100; i++)); do quot=$(bc <<< "scale=8; 3.1415926/2.7182818"); done; } +real 0m0.463s +user 0m0.116s +sys 0m0.364s |
