Data Structure issue
-
i have an assigntment thats says that we have an infinite amount of elements and we need to check how many of those elements have a specific value and i need to write algo in O(logn) how is that possibble, i mean you must go through all the elements..
Having an infinite amount of stuff like that doesn't really make sense. Unlimited perhaps, in the sense that there is no a-priori constant limit that you can abuse to make all algorithms collapse to constant time. But infinite, no way. Even if it's sorted, it could start with infinite zeroes, which you therefore cannot count, nor could any higher element ever be reached. It just doesn't work.
-
Having an infinite amount of stuff like that doesn't really make sense. Unlimited perhaps, in the sense that there is no a-priori constant limit that you can abuse to make all algorithms collapse to constant time. But infinite, no way. Even if it's sorted, it could start with infinite zeroes, which you therefore cannot count, nor could any higher element ever be reached. It just doesn't work.
Pi goes to inifinite decimal places .. creating the infinite output is easy and such things exist. Any irrational number is an example, the element involved being a digit. Even in your case a computer will get thru thousands or millions of compares for a single digit per second. If I asked you to count the digit 7 occurance in the PI output you can easily do it, and you could carry the count until you ran out of memory, disk space etc to hold the count. You only need the count you don't have to store the thing. Doing it in O (log n) that is the question?
In vino veritas
-
Pi goes to inifinite decimal places .. creating the infinite output is easy and such things exist. Any irrational number is an example, the element involved being a digit. Even in your case a computer will get thru thousands or millions of compares for a single digit per second. If I asked you to count the digit 7 occurance in the PI output you can easily do it, and you could carry the count until you ran out of memory, disk space etc to hold the count. You only need the count you don't have to store the thing. Doing it in O (log n) that is the question?
In vino veritas
Describing a procedure that produces infinite output is easy, yes. But you can never *have* all of its output, and no you cannot count the number of occurrences of the digit 7 in the decimal representation of PI. You can start to count, but you would never have the answer. That would technically not even be an algorithm, because an algorithm is an Effective Method, which means it must terminate in a finite number of steps.
-
Describing a procedure that produces infinite output is easy, yes. But you can never *have* all of its output, and no you cannot count the number of occurrences of the digit 7 in the decimal representation of PI. You can start to count, but you would never have the answer. That would technically not even be an algorithm, because an algorithm is an Effective Method, which means it must terminate in a finite number of steps.
I can't and wont agree, you can terminate any infinite processes on a different criteria Pi to the 100,000 place is a classic example as is counting. So even infinite processes can terminate in a finite number of steps you just don't get a full precision solution. Rounding, image analysis, smoothing, infinite searches and a pile of other fields all have solution infinite algorithms that if left run would never end. However you concluded them when you have sufficient accuracy for your needs and they are most definitely normally called algorithms. I even know several of them are patented as Algorithms even though under your definition they aren't because they would never end, except for they pick an point to terminate the processing. As a bit of humor I am not sure the field of Fractals knows it can't have algorithms because every calc in the field goes to infinity you have to force bailout :-) Given there are multiple definitions of Algorithm I will leave it up to the OP to work out with his teacher what definition of Algorithm they want to use. I am quite happy to call what they are doing an algorithm even if you are not and it will just become a pointless argument.
In vino veritas
-
I can't and wont agree, you can terminate any infinite processes on a different criteria Pi to the 100,000 place is a classic example as is counting. So even infinite processes can terminate in a finite number of steps you just don't get a full precision solution. Rounding, image analysis, smoothing, infinite searches and a pile of other fields all have solution infinite algorithms that if left run would never end. However you concluded them when you have sufficient accuracy for your needs and they are most definitely normally called algorithms. I even know several of them are patented as Algorithms even though under your definition they aren't because they would never end, except for they pick an point to terminate the processing. As a bit of humor I am not sure the field of Fractals knows it can't have algorithms because every calc in the field goes to infinity you have to force bailout :-) Given there are multiple definitions of Algorithm I will leave it up to the OP to work out with his teacher what definition of Algorithm they want to use. I am quite happy to call what they are doing an algorithm even if you are not and it will just become a pointless argument.
In vino veritas
-
You are trying to duck the problem some algorithms go on to infinity. Some fractals never terminate they are designed to spit differences, they run until you turn them off they are in every sense of the word infinite. You could also add machine learning AI, it never stops learning. It does stuff in between time, termination is not a requirement of getting usable output. At no point in either of these concepts do I need to specify a termination or need finite things. You could claim they might run out of resources but that is also the case to the question as posed by the OP. You are just applying a physical world restriction to bring in a terminate. However it's an algorithm long before it ever terminated and as a concept it does run forever it would never end of it's own choice. To me you are adding significance to infinity/finite which are just concepts. Abnormal or selected terminations are just a byproduct of the real world, to the algorithm they can be meaningless. I doubt we will agree on this stuff we are sort of differing around physical vs concept infinity. You are wanting to take a much harder literal approach than I would in programming an algorithm. All that ends up happening is things I will call an Algorithm you won't call that, you would call it something else a process, a system or the like.
In vino veritas
-
You are trying to duck the problem some algorithms go on to infinity. Some fractals never terminate they are designed to spit differences, they run until you turn them off they are in every sense of the word infinite. You could also add machine learning AI, it never stops learning. It does stuff in between time, termination is not a requirement of getting usable output. At no point in either of these concepts do I need to specify a termination or need finite things. You could claim they might run out of resources but that is also the case to the question as posed by the OP. You are just applying a physical world restriction to bring in a terminate. However it's an algorithm long before it ever terminated and as a concept it does run forever it would never end of it's own choice. To me you are adding significance to infinity/finite which are just concepts. Abnormal or selected terminations are just a byproduct of the real world, to the algorithm they can be meaningless. I doubt we will agree on this stuff we are sort of differing around physical vs concept infinity. You are wanting to take a much harder literal approach than I would in programming an algorithm. All that ends up happening is things I will call an Algorithm you won't call that, you would call it something else a process, a system or the like.
In vino veritas
I'm not bringing in any real world things. *The definition* of an algorithm says that it must terminate - that's not just something random I'm throwing in. That's just some distracting naming though.. infinite processes then, sure. And we could define an infinite process that starts to count the occurrences of a specific value in an endless list, but unlike some other examples you have mentioned, it does not make any progress. It does not approximate a goal. It has nothing to output until it is done, which it never will be. Counting occurrences in some prefix was not the question. The occurrences of an item in an infinite list fundamentally cannot be counted, except by a [supertask](https://en.wikipedia.org/wiki/Supertask), which is an interesting concept but not allowed in any reasonable model of computation. Speaking about doing it in O(log n) as OP does is even more pointless, there isn't even an input size to set n to. There is no question about whether that's possible or not, the entire question cannot be asked.
-
I'm not bringing in any real world things. *The definition* of an algorithm says that it must terminate - that's not just something random I'm throwing in. That's just some distracting naming though.. infinite processes then, sure. And we could define an infinite process that starts to count the occurrences of a specific value in an endless list, but unlike some other examples you have mentioned, it does not make any progress. It does not approximate a goal. It has nothing to output until it is done, which it never will be. Counting occurrences in some prefix was not the question. The occurrences of an item in an infinite list fundamentally cannot be counted, except by a [supertask](https://en.wikipedia.org/wiki/Supertask), which is an interesting concept but not allowed in any reasonable model of computation. Speaking about doing it in O(log n) as OP does is even more pointless, there isn't even an input size to set n to. There is no question about whether that's possible or not, the entire question cannot be asked.
Totally agree with you on the O (Log n) without more detail, I said that from outset. I still am intrigued by your first part so let me throw you two very famous algorithms. Quadratic sieve - Wikipedia[^] General number field sieve - Wikipedia[^] Both run forever and we rate them in MIPS-years because we expect them to never end. In fact I know several maths departments have had them running for years with prime numbers slowly being added to a file list as it finds them. This one has been going 9 years, and hasn't output a number in over a year and it may never put out another number ( Only the PRIME GODS know). Great Internet Mersenne Prime Search - PrimeNet[^] You will note the weird today stats on right hand side to even know it is still running and you may get a laugh from the youtube video about the notification failing and the discovery date being 3 months late. Wikipedia and everyone I know calls them an algorithm .. except they fail your definition they be finite and terminate :-) A prime number search meets the EXACT OP QUESTION, it is an infinite search and sieving is O(Log n) Prime Factorization using Sieve O(log n) for multiple queries - GeeksforGeeks[^] Sieve theory - Wikipedia[^] My problem is you can't guarantee you can do it without knowing the data behaviour and if I can sieve it. You claim such a thing can't be done and we shouldn't talk about it ... yet it exists :-). I keep answering because you keep making out some sort of authoritative answer, you insist on some definition but you never say by who, what authority?. I have shown you a number of computer programming fields who don't agree with that definition and things you say are impossible
-
Totally agree with you on the O (Log n) without more detail, I said that from outset. I still am intrigued by your first part so let me throw you two very famous algorithms. Quadratic sieve - Wikipedia[^] General number field sieve - Wikipedia[^] Both run forever and we rate them in MIPS-years because we expect them to never end. In fact I know several maths departments have had them running for years with prime numbers slowly being added to a file list as it finds them. This one has been going 9 years, and hasn't output a number in over a year and it may never put out another number ( Only the PRIME GODS know). Great Internet Mersenne Prime Search - PrimeNet[^] You will note the weird today stats on right hand side to even know it is still running and you may get a laugh from the youtube video about the notification failing and the discovery date being 3 months late. Wikipedia and everyone I know calls them an algorithm .. except they fail your definition they be finite and terminate :-) A prime number search meets the EXACT OP QUESTION, it is an infinite search and sieving is O(Log n) Prime Factorization using Sieve O(log n) for multiple queries - GeeksforGeeks[^] Sieve theory - Wikipedia[^] My problem is you can't guarantee you can do it without knowing the data behaviour and if I can sieve it. You claim such a thing can't be done and we shouldn't talk about it ... yet it exists :-). I keep answering because you keep making out some sort of authoritative answer, you insist on some definition but you never say by who, what authority?. I have shown you a number of computer programming fields who don't agree with that definition and things you say are impossible
No you're just confusing GIMPS with the algorithms they use. Primality testing can trivially be done in finite time even with trial division. The Lucas-Lehmer test that GIMPS spends most its time doing also runs in finite time. Even factoring can be done in finite time with trial division. QS and GNFS do not need infinite sieving, they need an amount of sieving that depends on the smoothness bound B, which (while typically analyzed heuristically) is definitely finite (for example, it doesn't need to be any higher than the number being factored - that's a terrible bound but it makes B definitely finite). GIMPS as a whole doesn't have an end in sight because they can just keep looking for more Mersenne primes, but it's a project, not an algorithm. You have not shown that anything that I have said does not exist actually does, you have called various things infinite that aren't, and named an example of an infinite process that isn't an algorithm. The one thing you could have mentioned that is slightly troubling in the face of the finiteness of algorithms is the class of Las Vegas algorithms, which seems to defy the definition. But they terminate in finite time with probability 1. As for the definition, it's on [wikipedia](https://en.wikipedia.org/wiki/Algorithm) among other places. See also [effective method](https://en.wikipedia.org/wiki/Effective\_method). Not authoritative enough? Check the sources.
-
i have an assigntment thats says that we have an infinite amount of elements and we need to check how many of those elements have a specific value and i need to write algo in O(logn) how is that possibble, i mean you must go through all the elements..
-
No you're just confusing GIMPS with the algorithms they use. Primality testing can trivially be done in finite time even with trial division. The Lucas-Lehmer test that GIMPS spends most its time doing also runs in finite time. Even factoring can be done in finite time with trial division. QS and GNFS do not need infinite sieving, they need an amount of sieving that depends on the smoothness bound B, which (while typically analyzed heuristically) is definitely finite (for example, it doesn't need to be any higher than the number being factored - that's a terrible bound but it makes B definitely finite). GIMPS as a whole doesn't have an end in sight because they can just keep looking for more Mersenne primes, but it's a project, not an algorithm. You have not shown that anything that I have said does not exist actually does, you have called various things infinite that aren't, and named an example of an infinite process that isn't an algorithm. The one thing you could have mentioned that is slightly troubling in the face of the finiteness of algorithms is the class of Las Vegas algorithms, which seems to defy the definition. But they terminate in finite time with probability 1. As for the definition, it's on [wikipedia](https://en.wikipedia.org/wiki/Algorithm) among other places. See also [effective method](https://en.wikipedia.org/wiki/Effective\_method). Not authoritative enough? Check the sources.
Interesting I need to give that some more thought to see if it works for me. Most of us mathematicians and programmers are obviously just lazy and call it the Mersenne Primes algorithm, we know there are a couple of small sub section algorithms running under it. I can honestly say I have never thought much about it until this question. The problem I have is if I take it out to computability like you have (and your link), Mersenne Primes is not an Algorithm, it's not an Effective method (it doesn't terminate) .. it's not anything and you ended up calling it a project .. which I now understand. A project to me is meaningless and while to you it's just a formal definition, I lose working meaning and I am not sure I want to go that far just to get a definition :-) What is common to all the group of things that are causing problems is they all expel intermediate results and it is the intermediate results that are more important than the "project" terminating (using your terms). I see where you are going but I need time to think about it because this is tricky with this class of problems, I am even needing to look carefully at the definition of computability. A couple of the fractal situations are probably classed as not computabile.
In vino veritas
