0

I want to enumerate numbers (between 1 to 10136 range) but so far, most tools and trick I tried would struggle after 109 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 1010), 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 1010 much faster than anything else mentioned, it still struggle for any range bigger than 1010 (and by extension, 10136).

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 10136 faster than GNU seq does?

  • Comments are not for extended discussion; this conversation has been moved to chat. – Jeff Schaller Jun 15 at 16:39
  • Well, it's feasible if the increment is sufficiently greater than 1. Using the calc arbintrary precision calculator to increment by 10^130 completes in about a minute: calc 't=10^136; i=10^130; for (f=1; f <= t; f=f+i) { print f; }' ; this prints to STDOUT, and can be piped, etc. Appending a | wc to the end shows the output is 1000000 lines, and 136888760 chars long. (For less monotonous output try changing 10^130 to 86!.) – agc Jun 16 at 4:48
  • Closers: this Q. is useful for users unfamiliar with computability problems. – agc Jun 16 at 4:54
  • Indeed! @agc wish this wasn't closed but i guess certain peoples are too entitled to their opinions and point of view :D Glad to see someone else thinking it would help to have a working answer to this. – Nordine Lotfi Jun 16 at 5:57
  • 3
    @NordineLotfi if the increment is greater than 1 as agc suggested, then it is a completely different question! It isn't even similar to what you are asking for here. It only prints 1000000 lines, that's nothing! You are asking for something that is astronomically large, not even remotely comparable to 1000000. – terdon Jun 16 at 8:02
18

It's impossible. There's no way to enumerate 10136 at all, no matter how you cut it.

There's about 1080 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 1090 numbers per second. Enumerating your sequence at this incredible pace will still take 1046 seconds, or about 1038 years. I don't think you're prepared to wait for that long.

| improve this answer | |
  • I'm sorry, but while what you said was somewhat already pointed by @Isaac on another comment, yours (being a post) isn't really helping... There is always a way, me (or you) not knowing it, doesn't mean it's definitely impossible. – Nordine Lotfi Jun 15 at 9:02
  • 3
    @NordineLotfi Please re-read my answer. It contains enough of a proof that it is truly impossible. – TooTea Jun 15 at 9:04
  • If you say so :) I can't speak for much since i didn't find a way yet, so my words may lack weight, but the truth that "it is possible" still remain... Then again i'm not here to be right or wrong, but to receive answers (when possible in this case) in this specific case. When i do find a way, i would answer my own question of course. – Nordine Lotfi Jun 15 at 9:07
  • 5
    @NordineLotfi This answer assumes that you can parallelize this task to every single atom in the universe, each one spitting out 10^90 numbers every second, and it would still take 10^38 years. If you want to go faster, you need more cores than there are atoms in the universe. – gronostaj Jun 15 at 10:49
  • 1
    @NordineLotfi "If the result is all I care about" - What does result mean in this context? – Hagen von Eitzen Jun 15 at 11:51
9

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 10136-9 = 10127times 1 minute or around 19025875190258751902587519025875190258751902587519025875190258751902587519025875190258751902587519025875190258751902587519

Years. Or, to write it a shorter way (but not a bit shorter in time to process) About 10129 YEARS. Supposedly, the universe started 13.8 billion years ago (13.8*109). We are talking of about 10121 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:

1015 × 1080 = 1095

That is still needing 10136-95=1041 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;
}

| improve this answer | |
  • Yes, i tried that (as already mentioned) and performed the same...though still no dice for 2^(136-9) :/ – Nordine Lotfi Jun 15 at 2:28
  • 2
    @NordineLotfi I was trying to convey the clear idea that that is impossible. Don't waste time on that, you will never succeed. – Isaac Jun 15 at 2:39
  • I appreciate the action, but it'll take more than that to make me think it's impossible! – Nordine Lotfi Jun 15 at 2:40
  • 5
    @NordineLotfi Grow and learn, have a great time searching for an answer. :-) – Isaac Jun 15 at 2:42
  • Recursion must be expensive, as is conversion to and from decimal text. The aim should be to work in octo-long ints (8 * 64-bit words) and pipe every value in 64 binary bytes. – Paul_Pedant Jun 15 at 20:05
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 :-)

| improve this answer | |
  • 2
    There is another cut which probably says it would consume (by a large factor) the entire energy of the Sun during its lifetime. Once the numbers are big enough, the Universe conspires against we mortals. Who would have thought those 5 characters "1e136" would cause so much trouble. "To see a World in a Grain of Sand. And a Heaven in a Wild Flower. Hold Infinity in the palm of your hand. And Eternity in an hour." – Paul_Pedant Jun 15 at 10:12
  • Well done! but as i said to Isaac, it'll take more than that to make me stop :D And while Mathematics (at least what you mentioned in great details) clearly say it's impossible, that still doesn't mean it is (depending on how you do it) Alas, my words have less weight than yours without tangible proof, thus I'll just congratulate you on those details that you added (didn't knew half of that to be clearly honest, thank you) Still doesn't mean I'll stop trying. – Nordine Lotfi Jun 15 at 10:12
  • 3
    You are missing the point. Something that is mathematically impossible is impossible. My proof is, granted, not a mathematical one – but a physical one (the 2nd best thing). It rests on the laws of thermodynamics. Trying to argue with those is the surest sign of crackpottery. I would advice you to do some introspection before you go on claiming that the most fundamental understandings we have of the universe are wrong and you are right. Even if you won't: I gave you an example whereby you'd at least have to do better than the technological state of the art. And spend 10^{95} years even then! – gspr Jun 15 at 10:17
  • @NordineLotfi you are still misunderstanding: we are all saying it is possible, it just won't finish in your lifetime. If you consider a solution that takes more time (way, way, way more time) than you will be alive "possible" then sure, it is possible. If, however, you would like it to finish before you die so you can see the result, then it will not be possible. – terdon Jun 15 at 14:00
  • 2
    @terdon Interesting use of the word "possible". Anything that is predicated on forestalling the heat-death of the universe strikes me as definitely a little iffy. Being as the requirement includes a Linux pipe, the next reboot is probably the most that can be hoped for. – Paul_Pedant Jun 15 at 15:03
4

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 10136 / 100 = 10134 nanoseconds to print out 10136 lines. 10136 nanoseconds is 3.1688739 x 10117 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 10106 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.

| improve this answer | |
3

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.

| improve this answer | |
  • The perl one won't work, actually. I mean, besides the obvious reasons, it won't even run. At least on my machine, perl -le 'BEGIN{use bigint}; for (1..1e136) { print $_ . ", "}' fails with Range iterator outside integer range at -e line 1. Which doesn't detract from your post, really. – terdon Jun 15 at 17:31
  • The first perl solution can not work as the .. operator is not overload to work with bigints in perl. You may change it to: perl -e 'use bigint; while ($i++<1e136) { print $i . ", "}; print "\n"' – Isaac Jun 29 at 1:09
3

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.

| improve this answer | |
  • irony alert? don't see what you meant by that, but, yeah, i did thought of using regex to put zeros as you described, just not sure how to do the last part (like you described after that)... Mind making an example? (with smaller digits range, maybe) – Nordine Lotfi Jun 15 at 9:48
  • 1
    Maybe later. Right now I'm working on my recursive irony irony-alert alert generator. – Paul_Pedant Jun 15 at 10:20
  • 1
    Meanwhile, you probably have time to read this short story by Arthur C Clarke (he of 2001 - A Space Odyssey): urbigenous.net/library/nine_billion_names_of_god.html The last line is particularly apt. – Paul_Pedant Jun 15 at 10:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.