Space Complexity of Number-theoretic Algorithms

  • Thread starter nworm
  • Start date
  • #1
31
0

Main Question or Discussion Point

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

Answers and Replies

  • #2
shmoe
Science Advisor
Homework Helper
1,992
1
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)
 
  • #3
31
0
Yes, I have. I have found examples where the time complexity of number-theoretic algorithms is discussed only.
 
  • #4
shmoe
Science Advisor
Homework Helper
1,992
1
Try

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

(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.
 
Last edited by a moderator:
  • #5
31
0
Thank you. This is very interesting links.
 
  • #6
31
0
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.
 
  • #7
644
1
I havent 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 wont 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
 
  • #8
31
0
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" [Broken]

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?
 
Last edited by a moderator:
  • #9
644
1
nworm said:
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" [Broken]
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 wouldnt want to work with unit cost RAM model.

-- AI
 
Last edited by a moderator:

Related Threads on Space Complexity of Number-theoretic Algorithms

  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
4
Views
9K
  • Last Post
Replies
6
Views
5K
Replies
6
Views
14K
Replies
12
Views
3K
  • Last Post
Replies
3
Views
3K
Replies
5
Views
3K
  • Last Post
Replies
3
Views
4K
Top