5 ms·

> This is standard terminology within programming and cryptography Within cryptography, yes, but in programming in general, absolutely not. The cryptographic

by twic 7y ago

> This is standard terminology within programming and cryptography Within cryptography, yes, but in programming in general, absolutely not. The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.

arghwhat 7y ago
> Within cryptography, yes, but in programming in general, absolutely not. I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. The reason for that I do not find this possible with classical computers is that no matter what you do, reading data from memory is an unavoidable variable time process. Do not that arbitrary sized inputs here imply that the input is meaningful and must all be processed. I do not see algorithms that do not process their inputs as candidates here, such as the elsewhere stated example of even/odd test which just read a single bit. I consider an algorithm that only reads a fixed amount of information from its input to be a fixed-input algorithm, regardless of the "full" size of its input. Of course, if you place an upper bound on the input, then you can pad in various ways, or possibly have algorithms whose execution time is inversely proportional to its input size, thus balancing itself. However, placing an upper bound also mean violating the "arbitrary" requirement entirely, thus disqualifying the algorithm. Do note that I'd actually be quite interested if you have examples of such algorithms.
- razorunreal 7y ago
  So binary search is not logn time because it only reads logn values from the input? To know which parts are not read you basically have to run the algorithm. I find your definition unhelpful.
- throwawaymath 7y ago
  > I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessing-an-element-in-an-array-take-constant-time https://stackoverflow.com/questions/7297916/why-does-accessi... EDIT: Corrected "search" to "access"
  - Drod718 7y ago
    Wouldn’t searching for an element in an arbitrary array of size n happen in O(n) time, while only accessing it is considered O(1)? I could understand the search case for something like a hash table being O(1) but does that also apply to your standard array?
    - throwawaymath 7y ago
      Ah, I misspoke. I meant "access", you're correct about searching. The original link I cited for explanation still applies.
- tanderson92 7y ago
  Depending on how expansive your idea of the model of ‘computation’ is, there is this old paper: http://zero.sci-hub.tw/1814/0efc01f09f718e409481a47ff90e98fc/louri1995.pdf http://zero.sci-hub.tw/1814/0efc01f09f718e409481a47ff90e98fc... TLDR: using optics for sorting
ChrisLomont 7y ago
>The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. The normal usage of the phrase "constant time" predates CS by centuries, and it is much closer in usage to the crypto version than the complexity version. Crypto uses the term "constant time" to mean same time for any input, while the general CS community uses O(1) to mean bounded time and also often uses complexity to hide log N terms. It also allows variable time, as long as it's bounded (and that sometimes allows hiding terms like log N or log log N...). A good example is most algorithms treat addition as a constant time operation, but, for example, addition of indices for lookups is not constant time when inputs are unbounded. So if you compute an index by addition and ignore the logN time to do the addition, then you fudged. Yet this is commonplace in complexity theory, which models many basic operations as constant time when they are not for unbounded inputs. For example, a "constant time" hash table operation, which often indexes arbitrarily large indices with addition, ignores the log N needed to add arbitrarily large indices. Thus crypto uses the phrase in the more precise, centuries old usage.

by twic 7y ago

arghwhat 7y ago

> Within cryptography, yes, but in programming in general, absolutely not. I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. The reason for that I do not find this possible with classical computers is that no matter what you do, reading data from memory is an unavoidable variable time process. Do not that arbitrary sized inputs here imply that the input is meaningful and must all be processed. I do not see algorithms that do not process their inputs as candidates here, such as the elsewhere stated example of even/odd test which just read a single bit. I consider an algorithm that only reads a fixed amount of information from its input to be a fixed-input algorithm, regardless of the "full" size of its input. Of course, if you place an upper bound on the input, then you can pad in various ways, or possibly have algorithms whose execution time is inversely proportional to its input size, thus balancing itself. However, placing an upper bound also mean violating the "arbitrary" requirement entirely, thus disqualifying the algorithm. Do note that I'd actually be quite interested if you have examples of such algorithms.

razorunreal 7y ago
So binary search is not logn time because it only reads logn values from the input? To know which parts are not read you basically have to run the algorithm. I find your definition unhelpful.
throwawaymath 7y ago
> I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessing-an-element-in-an-array-take-constant-time https://stackoverflow.com/questions/7297916/why-does-accessi... EDIT: Corrected "search" to "access"
- Drod718 7y ago
  Wouldn’t searching for an element in an arbitrary array of size n happen in O(n) time, while only accessing it is considered O(1)? I could understand the search case for something like a hash table being O(1) but does that also apply to your standard array?
  - throwawaymath 7y ago
    Ah, I misspoke. I meant "access", you're correct about searching. The original link I cited for explanation still applies.
tanderson92 7y ago
Depending on how expansive your idea of the model of ‘computation’ is, there is this old paper: http://zero.sci-hub.tw/1814/0efc01f09f718e409481a47ff90e98fc/louri1995.pdf http://zero.sci-hub.tw/1814/0efc01f09f718e409481a47ff90e98fc... TLDR: using optics for sorting

ChrisLomont 7y ago

>The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. The normal usage of the phrase "constant time" predates CS by centuries, and it is much closer in usage to the crypto version than the complexity version. Crypto uses the term "constant time" to mean same time for any input, while the general CS community uses O(1) to mean bounded time and also often uses complexity to hide log N terms. It also allows variable time, as long as it's bounded (and that sometimes allows hiding terms like log N or log log N...). A good example is most algorithms treat addition as a constant time operation, but, for example, addition of indices for lookups is not constant time when inputs are unbounded. So if you compute an index by addition and ignore the logN time to do the addition, then you fudged. Yet this is commonplace in complexity theory, which models many basic operations as constant time when they are not for unbounded inputs. For example, a "constant time" hash table operation, which often indexes arbitrarily large indices with addition, ignores the log N needed to add arbitrarily large indices. Thus crypto uses the phrase in the more precise, centuries old usage.