Improving BigInteger algorithms

[cosmic pine]

look at this garbage
https://github.com/Eczbek/xieite/blob/main/include/xieite/math/big_integer.hpp#L331-L339
stringifying 999^999 in base 10 takes over 30 seconds
what algorithms can i try implementing to improve this operator?

[crystal thunder]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[trim tundra]

are you implementing stringifying by doing repeated division by 10?

[cosmic pine]

.... perhaps

this must be improved anyway

[trim tundra]

there are better ways of doing that IIRC, don't remember what exactly they were

[cosmic pine]

yeah i need help finding better algorithms

[trim tundra]

division of bigints is O(n), so repeated division by ten is O(n^2) no matter how it is done

[cosmic pine]

multiplication is also not the best, it's basically long division

[trim tundra]

I think python had this problem so they decided to add an arbitrary cap to how long stringified numbers will be

[cosmic pine]

stupid

Improving BigInteger algorithms

so I know about the Karatsuba multiplication algorithm but it's more difficult to implement with how my structure stores data

I don't know about division or stringification

those are the main points i need to improve

[blazing cypress]

Looking through boost multiprecision they just divide by 10, but to print 999^999 takes very small amount of time, didn't measure it but less than a second for 3000+ charachter string

[spiral rock]

it might be useful to poke around in here: https://github.com/bluescarni/mppp/blob/master/include/mp%2B%2B/rational.hpp#L957-L1117

i've never dug into these types of libraries in detail, but it's something i plan on doing eventually. going off of some of the comments in there it seems like they're approaching some of these multiprecision operators in a similar way as gnu's GMP library. both are probably really good codebases to help identify performant algorithm examples to go off of.

[cosmic pine]

yeah it must be my division algorithm then

[blazing cypress]

Have a look at their code, or the GMP one as they seem to slit the interger into blocks then divide those blocks rather than divide the whole int

[spiral rock]

yeah it seems like mppp approaches this stuff in a similar way. the only reason i linked that when boost was already mentioned is that it seems to outperform boost according to their interger benchmarks: https://bluescarni.github.io/mppp/integer_benchmarks.html

[cosmic pine]

huh

[steel plank]

do polynomial multiplication and division using fft

https://cp-algorithms.com/algebra/polynomial.html#sievekingkung-algorithm

for example 234 can be represented as 210^2+310^1+4*10^0

[heavy hazel]

but that's basically base 10

if you already know the factors then you could just output those directly

[steel plank]

yes, i just mean it say that since you can treat numbers as polynomial, you can use fft or other type of transforms for big int operations

[lean pagoda]

I personally used a std::string for bigint operations once

[wet fox]

what value is there in ever having a base 10 string of more than a dozen digits.... humans are the only ones reading base 10.. and they don't bother to read beyond a dozen digits.

[blazing cypress]

So me can see how big big num is and scratch my little monke head and say "wow big num"

[lean pagoda]

Humans are the only ones reading anything

As for why, probably big calculations

Human population is getting larger than max uint I believe

[blazing cypress]

Dunno what this has to do with anything, but the human population is a lot smaller than a uint64 max value which you don't need a big num for

[lean pagoda]

I said uint, not uint64

I'm just saying numbers are catching up to the limits

[blazing cypress]

Yeah a uint really isn't that big in the grand scheme of things

[lean pagoda]

Discord/Twitter snowflakes are also uint64

Which means eventually these will run out

[blazing cypress]

??? what do you mean by snowflakes?

[lean pagoda]

Object ids

Like user ids

Channel ids

etc

[blazing cypress]

It will be a long time until there are 18,446,744,073,709,551,615 id's for example if my computer was running at full tilt 5.2 GHz, it would take 161984 years to fill up a uint64_t. And there certainly aren't that many ID's being made on twitter per second

[wet fox]

wrong.

[wet fox]

exactly!

[cosmic pine]

yeah base 10 won't be the fastest

[lean pagoda]

Who else

[cosmic pine]

(aliens)

duh

[wet fox]

have you been asleep the last year... there's this thing called chatgpt

[lean pagoda]

That's an AI created by humans...

It's not a living being

[wet fox]

so?

[lean pagoda]

Let me rephrase the statement:
"Humans are the only living beings that can read anyting"

Because by your logic std::istream is also a candidate

[cosmic pine]

i mean, overall, if not humans then the only other purpose is machines

[cosmic pine]

interesting,

but im not sure i can use it