Space Complexity of Number-theoretic Algorithms

[nworm]

Can you write an example where a space complexity of any number-theoretic algorithm is calculated? Thanks In Advance.

 

[shmoe]

Have you tried google? Try 'euclidean algorithm' and 'complexity', you'll get piles of examples where the time and space complexity is discussed. I'd expect most textbooks covering complexity would have an example from number theory as well (the euclidean algorithm is probably common here as well being a very 'classic' algorithm)

 

[nworm]

Yes, I have. I have found examples where the time complexity of number-theoretic algorithms is discussed only.

 

[shmoe]

Try

http://pharos.cpsc.ucalgary.ca/Dienst/UI/2.0/Describe/ncstrl.ucalgary_cs/1989-376-38

(first hit from "space complexity" euclidean algorithm)

You might want to check Andrew Odlyzko's webpage

http://www.dtc.umn.edu/~odlyzko/doc/cnt.html

It's filled with number theory algorithms, the handfull I've read included time and space complexity discussions.

 

[nworm]

Thank you. This is very interesting links.

 

[nworm]

Dear shmoe.

I have read the part of these links. Not long ago I read "A Course in Number Theory and Cryptography" by Neal Koblitz. I have used Neal Koblitz's model of bit operations for estimation of the time complexity of my algorithm.

If you read Neal Koblitz's book say please what do you think about next questions?
Is this model a RAM with infinity space and word length?
Can I speak that the space complexity of my algorithms is the number of bits using to story information?
Thanks In Advance.

 

[TenaliRaman]

I haven't read the book, but normally when we speak of time and space complexity, we do in terms of Turing Machine (commonly referred to as Turing Machine model). I presume you are aware of this and hence won't delve further into this.

Now when one speaks of RAM model, one has to be very precise as to which one he/she is referring to.

There are two types of RAM models,
1. General Unit Cost RAM model
Unit cost inucurred per instruction execution
2. Log-cost RAM model
Cost incurred per instruction execution is proportional to logarithm on the size of the operands

The general unit cost RAM model is much more powerful than our Turing Machine. The Turing Machine equivalent in RAM models is the log-cost RAM model. Hence, if you are using the RAM model, one normally should adhere to log-cost RAM model. However, working with unit-cost RAM model is simpler and hence we do a work around.

Work Around :
We make sure that all the input operands are polynomially bounded in the input size. For such a unit cost RAM model, there is an equivalent log-cost RAM model and thereby a Turing model.

Most algorithms (especially the number theoretic algorithms that you are interested in) today commonly appeal to unit-cost RAM model in the way i described above.

-- AI

 

[nworm]

Thank you.
If I understand rightly then you mean "the uniform cost criterion" and "the logarithmic cost criterion" from

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese1.html"

I deal with big numbers. So I think to use the logarithmic cost criterion, i.e. O(log N) units of space for a number N (or O(log N) bits for a number N). Am I right?

 

[TenaliRaman]

Thank you.
If I understand rightly then you mean "the uniform cost criterion" and "the logarithmic cost criterion" from

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese1.html"

Yes.

I deal with big numbers. So I think to use the logarithmic cost criterion, i.e. O(log N) units of space for a number N (or O(log N) bits for a number N). Am I right?

Sort of close but not completely. Our computers are known to simulate Turing Machines. As i said earlier, the unit cost RAM model is far more powerful than our Turing Machine. That is, a unit cost RAM model can outperform our computers at certain things and obviously, since we are looking at things that our computers are capable of doing, we wouldn't want to work with unit cost RAM model.

-- AI