search

apple / swift-numerics

Advanced mathematical types and functions for Swift
Apache License 2.0
1.67k stars 142 forks source link

[BigInt tests] ✅ String tests #244

Open LiarPrincess opened 1 year ago

LiarPrincess commented 1 year ago

Please read the #242 Using tests from “Violet - Python VM written in Swift” before.

All pass.

String parsing

I think that String parsing performance can be improved. 4000 cases with BigInts up to 1280 bits take ~40s on my laptop (2014 rMBP -> mac 11.7 (Big Sur), Xcode 13.2.1, Intel), Violet does this in 1.5s (there is a separate performance PR).

Violet secret:

Instead of using a single BigInt and multiplying it by radix, we will group scalars into words-sized chunks. Then we will raise those chunks to appropriate power and add together.

For example: 1_2345_6789 = (1 * 10^8) + (2345 * 10^4) + (6789 * 10^0)

So, we are doing most of our calculations in fast Word, and then we switch to slow BigInt for a few final operations.

Implemented here. Should I create an issue for this?

mgriebling commented 1 year ago

Noticed poor performance in the BigInt initializer from a string as well. See pull request # 261.