Added improved LosslessStringConvertible init() with "^=" bug fix.

mgriebling commented 1 year ago

Added improved LosslessStringConvertible init() with order of magnitude faster performance. Removed unnecessary _digits and _digitRadix. Fixed a copy/paste problem in "^=" function. (see Issue # 260) Added test cases for string conversion performance and logical operation tests.

Added a fix for division/remainder having incorrect signs. Also fixed a corner-case issue where negated integers weren't. Also added test cases for the division sign.

LiarPrincess commented 1 year ago

I looked more closely into the performance of swift_numerics implementation in PR-256: [BigInt tests][No merge] rabbit How NOT to write performance tests.

Results:

🐧 linux	swift_numerics	Violet	Violet XsProMax	attaswift
test_string_fromRadix8	0.778445 [±0.409%]	0.00225963 [±2.32%] (3.45e+02x)	0.00235958 [±4.21%] (3.3e+02x)	0.0739055 [±0.555%] (10.5x)
test_string_fromRadix10	0.714782 [±0.907%]	0.00377317 [±0.45%] (1.89e+02x)	0.00352649 [±1.73%] (2.03e+02x)	0.0764369 [±2.49%] (9.35x)
test_string_fromRadix16	0.576508 [±0.444%]	0.00165497 [±2.94%] (3.48e+02x)	0.00175369 [±0.792%] (3.29e+02x)	0.0476555 [±3.48%] (12.1x)

Each cell contains:

time in seconds
inside square brackets -> relative standard deviation
inside parens -> speedup vs the swift_numerics (which is the 1st column); 10.5x means 10.5 times faster

More details are available in the PR that I linked above, it also contains links to the Violet code. Disclosure: I am the author of the Violet implementations.

In your code you mention:

///  Speeds the time to initialize a BigInt by about a factor of 16 for
///  the test case of the string for 512! using radix 10. A radix 36 test
///  was 10X faster.

According to my tests we can do even better:

Radix	Possible improvement
8	345 times faster
10	189 times faster
16	348 times faster

Anyway, I don't think that this is the 'official' Apple implementation. I wrote a lot of unit tests for it (see: I-242: [BigInt] Using tests from “Violet - Python VM written in Swift”) and has a tendency to:

crash - 3/14 scenarios
return invalid result - 6/14 scenarios

So, it should NOT be used in production.

Written under covid. I'm basically an intellectual vegetable; may be unreadable. sorry!

mgriebling commented 1 year ago

Appreciate the feedback. Glad to know these times can be improved even more. I am a bit surprised by lack of support for this from Apple and that so many issues are unresolved. I do have my own version of BigInt (who doesn't 😉) and will continue on that. I was even original and called it Integer instead of BigInt.

Hopefully, one day, Apple will see the light and realize that a lot of people want better math support on the Mac and iDevices. For instance, why does no one have an "ipow" function yet. Or why don't the binary integers have x.squared() support which generally could be twice as fast as multiplying x * x.

Good work on Violet, BTW. The project looks very impressive.

apple / swift-numerics

Added improved LosslessStringConvertible init() with "^=" bug fix. #261