2

I am working on a Forth implementation where I have come across the need for double-cell arithmetic (the Forth implementation is 32-bit) including double-cell multiplication and division/remainder. However, the architecture I am developing this for, ARM Cortex-M4, lacks 64x64 multiplication or 64/64 division/remainder instructions (it only has 32x32 multiplication and 32/32 division and 32x32+64 multiply/accumulate instructions).

While I would be fine with 32x64 multiplication (as 64x64 multiplication can be emulated with it for cases that would not overflow anyways), and for some things 64/32 division/remainder would be sufficient, I would like to at least have a full 64/64 division/remainder in addition to 32x64 multiplication so I can do a full implementation of double-cell arithmetic.

phuclv
  • 37,963
  • 15
  • 156
  • 475
Travis Bemann
  • 133
  • 6
  • see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) Karatsuba is your friend. anyway here [my ALU32 implementation](https://stackoverflow.com/a/26603589/2521214) doing the 64=32x32 operation using 32=16x16 operations only so you can do the same for twice the bit width ... division is there too but that can be done much better I think ... – Spektre Apr 16 '20 at 07:47
  • just like you can use the 32x32 to create as large of a multiplier as you want (memory and flash are your limits there), you can use the divider as well. in the same way that you use grade school math to make the multply work you make the divide work you are starting from the msnumber of the numerator and walking the denominator from left to right through it. division should be easier than multiply in this case to implement. That or you just write the code and let the compiler/linker insert its own optimized 64 bit multiply or divide code – old_timer Apr 16 '20 at 22:41
  • try a line or two of C to do the larger math then see what the compiler outputs then just make calls to those directly if you wish. – old_timer Apr 16 '20 at 22:41

1 Answers1

3

You can take as an example the bigmath.f library (or another variant) — Double Number Arithmetic by Wil Baden.

There are defined D* and DU/MOD words.

Regarding a license. I think this code is in public domain. It was published in Forth Dimensions1 as a reference implementation, and the author said there: "For a copy of the source for this article send e-mail requesting Stretching Forth #19: Double Number Arithmetic".

For DU/MOD word, Wil Baden also noted: "The algorithm is based on Knuth's algorithm in volume 2 of his Art of Computer Programming, simplified for two-cell dividend and two-cell divisor".

1 Wil Baden (1998). Stretching standard Forth #19: Double Number Arithmetic. Forth Dimensions XIX.6 March-April 1998, pp. 33-34

On the page 4 we can also read:

The material contained in this periodical (but not the code) is copyrighted by the individual authors of the articles and by Forth Interest Group, Inc., [...] Any code bearing a copyright notice, however, can be used only with permission of the copyright holder.

And it seems neither the code nor the article bears any copyright notice.

ruvim
  • 7,151
  • 2
  • 27
  • 36
  • Thanks. Unfortunately, as I bet that code is under a proprietary license, I cannot directly use or derive that code. (My code is GPL3; I personally would prefer BSD3 but I am borrowing code from another Forth which is GPL3.) – Travis Bemann Apr 15 '20 at 13:48
  • I think, the code is in public domain. I have updated the answer. – ruvim Apr 15 '20 at 18:46