Thread: Stacks and arithmetic expressions

Originally Posted by +Azazel+

Hello again,

While working on the assignment, it turned out that its actually the numbers that can be infinite not the length of the chain. So I might be multiplying digits that are larger than what a variable can hold. Ive been looking through the Karatsuba method and Schönhage-Strassen algorithm for multiplication but I was unable to find any algorithms like that in C. Perhaps someone knows of any algorithms for multiplication, division, addition, or subtraction?

Second question: Is there a way to access the L1 and L2 cache and use a tiny bit of it for an operation? So as to speed up the program?

Thank you!

This is a good resource - wouldn't bother about efficiency at this time - just make it work with one of the simple methods described:
http://en.wikipedia.org/wiki/Multiplication_algorithm

A quick google for other math operations should be fairly easy - and add/subtract are really easy to do with string operations. Just need a loop and a carry to the next value. Normalizing the values [making them equal length] will make the rest of the math simpler.

Divide will certainly be hardest - but as long as you are happy to be inefficient, I'd say that it's fine.

As to using the cache - the processor will automatically use the cache when you are accessign data that you have recently used - it loads ALL data that you use into the L1 cache, and if you re-use it before it's been shuffled out of the L1 cache, it will be used from there. It is actually more of a problem to AVOID using the cache when working on really large problems - those where you KNOW that the data will not be re-used, and thus makes no sense to store in the cache. But I doubt you'll have that particular problem here, as caches on modern processors are severa hundred kilobytes, even into the megabytes for the latest models.

--
Mats