search

sasagawa888 / eisl

ISLisp interpreter/compiler
Other
281 stars 23 forks source link

karatuba maltiplication #178

Closed sasagawa888 closed 2 years ago

sasagawa888 commented 2 years ago

Multiplication by the karatsuba algorithm is effective for bignum that is not very large.

sasagawa888 commented 2 years ago

It worked partially. Recursion is incorrect.

(eisl-test (expt 8 100) (expt 9 100)) 541065251157864887211041106500951546849198083650605175631231999311595717627039750725653834516531293192786380424503345814918785318111465779185310398101365179531660546590048939925491941376 (* (expt 8 100) (expt 9 100)) 541065251157864887211041106500951546849198083650605175631231999311595717627039750725653834516531293192786380424503345814918785318111465779185310398101365179531660546590048939925491941376

sasagawa888 commented 2 years ago

Fixed it.

(eisl-test (expt 9 300) (expt 8 300)) 158397721232952157099663331662058396308396888111045869981209555484061457483208619094996765089871097105864496667718477019329051222441824036194899741754170876942943265284269276382472012925956593227422823874948662302373147631300840051813354534202789930395743160943801332422672183429431348640639445646050136281173156298154035426694020881286748217686783312239643807518290458076561280670915869793518710763420140700002417503557747541672889434457459190138049069474395813871996264693779709853488855754245495278862217546765120096372388235350892832968182978425573605376 (* (expt 9 300) (expt 8 300)) 158397721232952157099663331662058396308396888111045869981209555484061457483208619094996765089871097105864496667718477019329051222441824036194899741754170876942943265284269276382472012925956593227422823874948662302373147631300840051813354534202789930395743160943801332422672183429431348640639445646050136281173156298154035426694020881286748217686783312239643807518290458076561280670915869793518710763420140700002417503557747541672889434457459190138049069474395813871996264693779709853488855754245495278862217546765120096372388235350892832968182978425573605376

sasagawa888 commented 2 years ago

I incorporated karatsuba multiplication to mult.

sasagawa888 commented 2 years ago

when large bignum , still buggy.

sasagawa888 commented 2 years ago

It seems correct if the product is multiplied by about 10,000 digits. The Karatsuba method is slow for large numbers. I decided to leave it to NTT for a large number.