search

attaswift / BigInt

Arbitrary-precision arithmetic in pure Swift
MIT License
765 stars 107 forks source link

Computational overhead #2

Closed SummonY closed 7 years ago

SummonY commented 8 years ago

hello,

Thank you for open source this Arbitrary-precision arithmetic. When I use this to test paillier algorithm computational overhead, this function

func power(exponent: BigUInt, modulus: BigUInt) -> BigUInt{}

, the Java modPower computational overhead about 45ms but this function about 2.7s, cause some distortion. The overhead test code at here: https://github.com/SummonY/Paillier_iOS

Can you help to optimize this function?

Thanks, Summon Yang

lorentey commented 8 years ago

Interesting! I'm sure power can be improved; if you know a better algorithm than the right-to-left binary method it currently uses, I'd love a pointer to it. (Or even better, a pull request that implements it!)

2.7s vs 45ms seems a bit slow; is that a single function call? How many digits are there in the arguments?

SummonY commented 8 years ago

Yes, it is a single function call. They both use 1024 digits. Ok, I will see the source code of Java modPower when I have time.

serieuxchat commented 7 years ago

(Numbers corrected below) We would be interested in some performance improvements as well. Trying to use the library for SRP protocol implementation, and, unfortunately, exponentiation of 2100 bit integers takes around 30 seconds on the Simulator and around 7 seconds on an iPhone 7 :-(

lorentey commented 7 years ago

Can you give a concrete example of an expression that is slow to compute?

serieuxchat commented 7 years ago

Here is an example of a long computation:

g.power(a, modulus: N)

g = 2

a = 50BF3A20EBF53DD3CA79620CE47928148A15B25B28D00B25687AA08ABFA455E8641416DF9985A08521D719177D83A33C3B64AD5DA4BC3320C499220D1EF83ABAC9A10F04C44262540DD39FE9ABC590F774906589C72DF4439F63C9D0CE3545B497A8DFB8BDEB97CE2F7521FDB1AD55CE3E23B3634FC1AD2F40E63D68BBB6C0B25526F1729DDFA5130DEFDD142EB8433020C9211D08D6F59B3C3C90BD8FB258BCDF5A2FF87F77E2C427517D55C5C2BE25B9BC923DEB9BEDA25B505E09C5EEA44D584FAF0648DF23A8757B6414B9BF95E5F51C3910C97E70134E6A16A23F8F6AE8068AE01A6E9CE090DD02F6C2EAD70D1918CBFAAB58C78DC565E0B2479D9E51AC

N = E13803363DBE8FC19F85E7DC6E8C26ACE2D78D722C1DE8A17746206BC436EC5BF20C0ACCE8BDACED9F22939836879E31D8F69ABFD7F357A1FA9DF31A3E5AF764E7D3D1CEAF48FF3C28F14004651FDB2D81C0B4E0DE6FD1EA7975BB868AFF65CB163F29205992ED2D80A7055A5BFA8C96456D74E6BA19ECCD4E3F3AE31B2D368DBC627EC3F701423586F77BA76E5A552DBA821DF7241B4FF43E7BDD5BCC55EEB2DBE2120B33F3D4A0EF4A3EA5B9EF8C2DC33447CEC468DD86B7AA23E3005305007433D51EC866228326B38EBED72C582CE121E95544FA08703B51E73F4EED91C26851573D01DDF189C710C29E9DBB4ED382942AF8590BB7AE33BF04FF40D8A003

lorentey commented 7 years ago

Awesome, thank you.

serieuxchat commented 7 years ago

Tried the same operation with imath (https://github.com/creachadair/imath/blob/master/imath.h) - takes 0.15 ms (48 times faster)

lorentey commented 7 years ago

Are you using Debug or Release builds? I can reproduce multi-second calculations only in Debug mode; in Release builds, the example you gave takes about 0.23 s on my CPU. (Unoptimized builds are 20x-40x slower.)

Also, is the imath result 0.15 ms or 0.15 s? (0.15 ms would cause a great deal of concern to me; but your quoted 48x slowdown indicates 0.15s might be the correct value.)

lorentey commented 7 years ago

I'm closing this issue as it seems the reported performance problems were measured in Debug (i.e., non-optimized) builds.

Please reopen the issue if you're able to reproduce slow performance in optimized builds.