Faster way to enumerate number than GNU seq? [closed]

Question

I want to enumerate numbers (between 1 to 10¹³⁶ range) but so far, most tools and trick I tried would struggle after 10⁹ numbers or so...

Here some examples (with smaller range):

For seq 99999

real    0m0.056s
user    0m0.004s
sys     0m0.051s

For seq 9999999

real    1m5.550s
user    0m0.156s
sys     0m6.615s

So on so forth... Thing is, it start to struggle only after the 9th number or so (in this case, 999999999) and on ward. I thought of splitting them in smaller range and running them in parallel:

cat <(seq 000 999) <(seq 999 1999) <(seq 1999 2999) <(seq 2999 3999) <(seq 3999 4999) <(seq 4999 5999) <(seq 5999 6999) <(seq 6999 7999) <(seq 7999 8999) <(seq 8999 9999) <(seq 9999 10999) <(seq 10999 11999) <(seq 11999 12999) <(seq 12999 13999) <(seq 13999 14999)

real    0m0.258s
user    0m0.008s
sys     0m0.908s

which is considerably slower (especially with bigger range as it goes on) than seq 000 14999

real    0m0.042s
user    0m0.000s
sys     0m0.041s

I tried a perl script i found on SO:

#!/usr/bin/perl
use strict;
if ( ($#ARGV+1)!=2 ) { print "usage $0  \n"; }
my @r = &bitfizz( $ARGV[0], $ARGV[1] );
for(@r){ print "$_\n"; }
sub bitfizz() {
    $_[0]=join( ",", split(//, $_[0] ) );
    for( my $i=1; $i<=$_[1]; $i+=1 ) { $_=$_."{$_[0]}"; }
    @r=glob( $_ );
}

with perl script.pl "0123456789" 10* But while it seemed faster than seq (when doing anything less than 10¹⁰), it still struggle and seems like it would take forever to complete...

I don't need to write the enumerated numbers to a file, but i do need it to be on stdout, so that i can process it.

EDIT:

@Isaac mentioned in his answer (and in the comment) something that could work, and while it does goes through 10¹⁰ much faster than anything else mentioned, it still struggle for any range bigger than 10¹⁰ (and by extension, 10¹³⁶).

Worth mentioning since it was mentioned as a possible duplicate to this post (which it technically isn't).

How do i enumerate from 0 to 10¹³⁶ faster than GNU seq does?

Answer 1

It's impossible. There's no way to enumerate 10¹³⁶ at all, no matter how you cut it.

There's about 10⁸⁰ atoms in the observable universe, in total. Imagine the limit of total parallelization where you manage to harness the power of every single atom out there. If every atom takes 100 picoseconds to spit out a single number (which means a clock frequency of 10 GHz, so way faster than current computers), you get 10⁹⁰ numbers per second. Enumerating your sequence at this incredible pace will still take 10⁴⁶ seconds, or about 10³⁸ years. I don't think you're prepared to wait for that long.

Answer 2

The answer has already been written in

All possible combinations of characters and numbers

Use the c source code, change the charset to only 0123456789 and execute.

It takes only

➤ time ./permute.out 5 >/dev/null
run    : 0m0.012s sec

➤ time ./permute.out 7 >/dev/null
run    : 0m0.764s sec

➤ time ./permute.out 9 >/dev/null
run    : 1m12.537s sec

In a old and slow machine.

But I warn you, even with a small C code the time is proportional to the length of the permutation. A 136 permutation length is in the order of 10^136-9 = 10¹²⁷times 1 minute or around 19025875190258751902587519025875190258751902587519025875190258751902587519025875190258751902587519025875190258751902587519

Years. Or, to write it a shorter way (but not a bit shorter in time to process) About 10¹²⁹ YEARS. Supposedly, the universe started 13.8 billion years ago (13.8*10⁹). We are talking of about 10¹²¹ universe lives. Good luck with that!!.

Please understand, everything takes time. Even a very small time, a femtosecond (a ray of light travels approximately 0.3 μm (micrometers) in 1 femtosecond, a distance comparable to the diameter of a virus) per number and with a extremelly high amount of computers (as many as atoms there are in the universe) will yield:

10¹⁵ × 10⁸⁰ = 10⁹⁵

That is still needing 10^136-95=10⁴¹ seconds to complete.

Source code

Source code edited:

#include <stdio.h>

//global variables and magic numbers are the basis of good programming
const char* charset = "0123456789";
char buffer[200];

void permute(int level) {
  const char* charset_ptr = charset;
  if (level == -1){
    puts(buffer);
  } else {
    while( (buffer[level] = *charset_ptr++) ) {
      permute(level - 1);
    }
  }
}

int main(int argc, char **argv)
{
  int length;
  sscanf(argv[1], "%d", &length); 

  //Must provide length (integer < sizeof(buffer)==200) as first arg;
  //It will crash and burn otherwise  

  buffer[length] = '\0';
  permute(length - 1);
  return 0;
}

Answer 3

Let's take a slightly different approach. Assume it is indeed possible to do this. How, then, do you print it? Take this trivial C program:

#include <stdio.h>
void main(){
  int i;
  for(i=1;i<=100;i++){
    printf("%i\n",1);
  }
}
    

That simply prints out the number 1 one hundred times. I ran this 100 times and timed it, the average time taken per run was:

$ time ./printOne >/dev/null

real    0m0.004s
user    0m0.001s
sys     0m0.003s

So, around 0.004 seconds, that's one millisecond on my relatively powerful laptop. Let's be generous though and imagine a machine orders of magnitude faster, let's say it can print 100 lines in one nanosecond (10^-9 seconds, or 0.000000001 seconds), so 1000000 times faster.

Now, let's also ignore the time it would take to actually calculate the numbers and let's just imagine that a magical solution calculates them in no time. So now, all we have to do is use our super fast printing program to print out these numbers. Since we know it can print out 100 lines in one nanosecond, that means it will take 10¹³⁶ / 100 = 10¹³⁴ nanoseconds to print out 10¹³⁶ lines. 10¹³⁶ nanoseconds is 3.1688739 x 10¹¹⁷ years, just to print out the data without even calculating it! And, because that number isn't easy to understand, it means this many years:

31688739000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

The estimated time for the heat death of the universe is around 10¹⁰⁶ years from now. This means that only to print your data would take a computer that is orders of magnitude faster than anything we have more time than the rest of the life of the entire universe. In fact it will take orders of magnitude more time than the life of the universe.

So sure, while you could argue this is actually possible, it is a very useless meaning of the word possible since any way you look at it, neither us nor the universe we rode in on will be around by the time it finishes. Printing.

Answer 4

This is meant to follow up on TooTea's excellent answer, since OP's comments to that seems to indicate that they seriously misunderstand the nature of the problem they're posing.

Landauer's principle, which follows from thermodynamics, sets a lower bound on the amount of energy necessary to change one bit of information (in any medium!) at k·T·ln(2), where k is Boltzmann's constant and T is the temperature of the system.

Taking the best experiment I could find (state of the art in 2016), a lab managed to do some bit flips at 4.2 zJ (4·10^{-21} J). As we can expect from Landauer's principle, they did this by very carefully cooling down the physical system in which the bit flips were happening.

Supposing you had some way of enumerating numbers by only flipping a single bit for each number (you don't), you'd need 4.2·10^{-21}·10^{136} ≈ 10^{115} J to do the enumerating. In 2017, all of humanity combined produced about 159 PWh of useful energy, across all forms. That's 3.6·10^3·159·10^{15} J/year ≈ 6·10^{20} J/year.

This means that if you harnessed all of the entire species' energy production and managed to scale a state of the art lab experiment to consume all of that energy, it'd still take you about 10^{95} years to do your enumeration.

Stop trying :-)

Answer 5

I want to enumerate numbers (between 1 to 10^136 range)

and the answers you are already getting should be telling you why you won't.

Or, yes, you can enumerate then:

#!/usr/bin/perl
use bigint;
for (1..1e136) { print $_ . ", "}

but it'll take an awful lot of time. As in ... much longer than you can expect to live. Let's have some fun with seq, shall we?

j=9 TIMEFORMAT='%lR';  \
for i in `seq 1 9`; do 
    j=$(( $j * 10 + 9));
    echo -n "$i digits: ";
    time seq $j > /dev/null; 
done

I get

1 digits: 0m0,002s
2 digits: 0m0,002s
3 digits: 0m0,001s
4 digits: 0m0,002s
5 digits: 0m0,014s
6 digits: 0m0,126s
7 digits: 0m1,261s
8 digits: 0m12,631s
9 digits: 2m9,607s

As you can see, the startup time dominates up to and including 9,999, but then the time rises by about a factor 10 for each digit --- totally expected since you have 10 times more numbers to handle. And it will go on ...

  8 digits:~   0.2 minutes
  9 digits:~   2   minutes
 10 digits:~  20   minutes
 11 digits:~ 120   minutes (2 hours)
 36 digits:~ 2e25  hours   (> 3,500 years)
136 digits:~ 2e125 --- never mind.

That is a good while longer than your rest lifespan. And if you find a way to make that 100 times faster(!), you'd still wait 3.5 years for 1e36 --- never mind 1e136 digits. This is simply not sustainable. (Which is what everybody else was saying, but maybe this helps you understand.)

If you would tell us what you actually try to do you might get better answers. Maybe you need promises and delays execution, maybe you need a database, ... but I am sure you do not need to enumerate all of it.

Answer 6

It's easy. Start at the top end of the values.

Print (to a file) all the nine-digit values from 000000000 to 999999999, followed by 127 zeroes. (136 = 9 + 127).

Then process that recursively, replacing the zeros in each line in places 10-18 with the whole sequence of nine-digit values for each of the initial rows. Then work on places 19-27 and so on.

That only recurses 15 times, so it should be quite fast. And you get a freebie at the end, because you only have one digit to deal with there (136 = 15 * 9 + 1).

You might want to prove the algorithm is correct first with smaller numbers, e.g. generating up to a million with two sets of 000-999. In fact, also time it with three sets of 00-99 and decide which is more efficient. I'm sure that process will be scaleable.

This answer should carry an irony alert, but I feel we are already way beyond that stage.

EDIT: This is an example script as requested, in Bash. It works on the numbers as characters, starting from the most significant digits, and appending a number of digits in each level of recursion. It is actually quite cute in its own right. It's as slow as a horse-drawn plough, but where you're going, that won't matter.

#! /bin/bash
#.. Forever: List a recurrent pattern.
#.. Forever repeat digits ...
#.. Forever 3 {00..99}
#.. will output 000000 to 999999 using 3 levels of recursion, each of 2 digits. 

#.. Append a stripe of width N to the incoming stream. 

function Stripe {

    local Row Add 
    
    while read Row; do 
        for Add in ${Digs[@]}; do
            printf '%s%s\n' "${Row}" "${Add}"
        done    
    done    
}

#.. Work through all the levels. 

function Recurse {

    local Deep="${1}"
    
    if [[ "${Deep}" -le 1 ]]; then
        Stripe  
    else    
        Stripe | Recurse $(( Deep - 1 ))
    fi
}

#.. Recursively output a numeric sequence.

    Repeat="${1:-2}"; shift

    #.. Make the digits list.
    Digs=( ${@} )
    [[ ${#Digs[@]} -eq 0 ]] && Digs=( {0..9} )

    #.. Make the full length repetitions.
    echo | Recurse "${Repeat}"

Sample tests:

Paul--) time ./Forever 3 A B
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB

real    0m0.018s
user    0m0.004s
sys 0m0.008s
Paul--) time ./Forever 2 {00..99} > foo1

real    0m0.400s
user    0m0.304s
sys 0m0.088s
Paul--) time ./Forever 4 {0..9} > foo2

real    0m0.428s
user    0m0.352s
sys 0m0.084s
Paul--) head -3 foo1
0000
0001
0002
Paul--) tail -3 foo1
9997
9998
9999
Paul--) diff foo1 foo2
Paul--) time ./Forever 3 {00..99} > foo3

real    0m37.789s
user    0m30.984s
sys 0m7.064s
Paul--) wc -l foo{1,2,3}
  10000 foo1
  10000 foo2
1000000 foo3
1020000 total
Paul--) 

But the whole idea was a poor joke. It does not matter which end of the number strings you start, the number of combinations is the same. I put in the suggestion that it only recurses 15 deep, if you work with 9-digit strings. That covers up the fact that the first level of recursion gets called a billion times, and the second level gets called a billion billion times, and the third level gets called 10^27 times.

You might as well waste your time on building a perpetual motion machine, or squaring the circle, or finding the last prime number, as continuing with this problem.