- #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.

- Thread starter nworm
- Start date

- #1

- 31

- 0

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

- #2

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

- #3

- 31

- 0

- #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.

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

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

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?

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

Yes.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]

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.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?

-- AI

Last edited by a moderator:

- 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

- Last Post

- Replies
- 12

- Views
- 3K

- Last Post

- Replies
- 3

- Views
- 3K

- Replies
- 5

- Views
- 3K

- Last Post

- Replies
- 3

- Views
- 4K