About those memory allocations:
Firstly the good news: By rearranging how things are done in my additions and subtractions, and judicious use of "const" and "inline" on the methods, the fibo(4784969) is now 20% faster.
As was already stated (I think by you), there is no reason to allocate mem and copy for each split in the multiply routine, so why do you do it that way? Is there a reason you avoid using a shared block allocation for this instead of running wild around memory?
It's my project. I will write it how I like
Like you I had never even heard of karatsuba til this thread happened. So I wanted to be able to write myself one from scratch, no peeking at other peoples code. To that end I wanted to keep things as simple as possible. Just so I know I have the algorithm down pat. Ergo no worrying about details like memory allocations.
Now that working well and I understand what karatsuba should do exactly step by step, I can get down to the problem of optimizing it. Which may include a total rewrite! But see below...
Wonder if Heater thought about doing static allocations.
Depends what you mean. If it's allocated it not static now is it?
I have certainly thought of the obvious thing, alloc all the memory you need at start up then manage where all your big ints are inside it manually, then release all the memory in one go at the end. This has been discussed here before.
Now, I want to keep my fibo() function as it is. This is C++, we are using operator overloading, might as well do it in C otherwise. So the question is: How to we do that thing with memory allocation whilst keeping the API the same?
An answer might be to replace "new" and "delete" with ones own memory allocator. That memory allocator would grab a big block of memory when initialized, then dole it out as needed, releasing it in one go at the end. That would pretty much do what ejolson has done in C I believe.
Then there is some low hanging fruit: As we said before high() and low() need not create new big ints. They only need to provide views into what exists already, no allocation, no copying.
Of course that depends on not changing the thing that one is taking the high/low of. For example this would fail:
Code: Select all
bint x = "79763491934591549154";
bint y = high(x);
x = "0";
// Now y is corrupted
We don't need to do that of course, and can prevent others from doing it my making high/low private methods.
Memory in C++ is a leaky abstraction .