multi-precision seq command

multi-precision seq command

%./mpseq 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
12000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
14000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002
16000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
18000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005

source code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DIE() die(__FILE__, __LINE__, __func__)
void
die(const char *file, const int line, const char *func)
{
   fprintf(stderr, "%s:%d: died in function %s.\n", file, line, func);
   exit(1);
}

#define max(a, b) (a > b ? a : b)

typedef unsigned long unit;

// array is BCD (binary coded decimal), LE (little endian)
// len is the number of UNITs
struct mp {
   unit   *array;
   size_t  len;
};
#define MP_UNIT     1000
#define MP_UNIT_LOG 3

// pass uninitialised mp
void
mp_init(struct mp *mp, size_t len)
{
   mp->array = malloc(len * sizeof *mp->array);
   mp->len   = len;

   if (!mp->array) DIE();
   for (size_t i = 0; i < len; i++)
      mp->array[i] = 0;
}

// pass used mp
void
mp_free(struct mp *mp)
{
   free(mp->array);
   mp->array = NULL;
   mp->len = 0;
}

// pass uninitialised mp as to
void
mp_copy(struct mp *to, const struct mp *from)
{
   to->array = malloc(from->len * sizeof *from->array);
   to->len   = from->len;

   if (!to->array) DIE();
   for (size_t i = 0; i < from->len; i++)
      to->array[i] = from->array[i];
}

// pass uninitialised mp
void
mp_read(struct mp *mp, const char *s)
{
   const size_t len_s = strlen(s);
   const size_t len   = (len_s - 1) / MP_UNIT_LOG + 1;
   if (!len_s) DIE();

   mp_init(mp, len);
   unit *a = mp->array;

   for (int i = 0; i < len_s; i++) {
      size_t pos = (len_s - i - 1) / MP_UNIT_LOG;
      if (s[i] < '0' || s[i] > '9') DIE();
      int n = s[i] - '0';
      a[pos] = a[pos] * 10 + n; }
}

void
mp_print(const struct mp *mp)
{
   int f = 0;

   for (int i = 0; i < mp->len; i++) {
      unit a_i = mp->array[mp->len - i - 1];
      char buf[MP_UNIT_LOG];
      for (int j = 0; j < MP_UNIT_LOG; j++) {
         int pos = MP_UNIT_LOG - j - 1;
         buf[pos] = a_i % 10 + '0';
         a_i /= 10; }
      for (int j = 0; j < MP_UNIT_LOG; j++) {
         if (!f && buf[j] != '0') f = 1;
         if (f) putchar(buf[j]); } }
   putchar('\n');
}

void
mp_dump(const struct mp *mp)
{
   for (int i = 0; i < mp->len; i++) {
      unsigned long n = mp->array[i];
      printf("[%ld]", n); }
   putchar('\n');
}

// pass uninitialised mp as ans
void
mp_add(struct mp *ans, const struct mp *mp0, const struct mp *mp1)
{
   int c = 0;
   int len = max(mp0->len, mp1->len) + 1;

   mp_init(ans, len);

   for (int i = 0; i < len; i++) {
      const unit n0 = i < mp0->len ? mp0->array[i] : 0;
      const unit n1 = i < mp1->len ? mp1->array[i] : 0;
      const unit nt = n0 + n1 + c;
      const unit n = nt >= MP_UNIT ? nt - MP_UNIT : nt;
      c = nt >= MP_UNIT ? 1 : 0;
      ans->array[i] = n; }

   if (!c) ans->len--;
}

int
mp_cmp(const struct mp *mp0, const struct mp *mp1)
{
   int r = 0;
   int len = max(mp0->len, mp1->len);

   for (int i = 0; i < len; i++) {
      const unit n0 = i < mp0->len ? mp0->array[i] : 0;
      const unit n1 = i < mp1->len ? mp1->array[i] : 0;
      if (n0 < n1) r = -1;
      if (n0 > n1) r =  1; }
   return r;
}

void
usage(void)
{
   fputs("usage: mpseq [first [inc]] last\n", stderr);
}

int
main(int argc, char **argv)
{
   const char *s_first, *s_inc, *s_last;
   switch (argc - 1) {
   case 1: s_first =     "1", s_inc =     "1", s_last = argv[1]; break;
   case 2: s_first = argv[1], s_inc =     "1", s_last = argv[2]; break;
   case 3: s_first = argv[1], s_inc = argv[2], s_last = argv[3]; break;
   default:
      usage(); exit(1);
   }

   struct mp first, inc, last;
   mp_read(&first, s_first);
   mp_read(&inc,   s_inc);
   mp_read(&last,  s_last);

   for (;;) {
      if (mp_cmp(&first, &last) > 0) break;
      mp_print(&first);
      struct mp tmp;
      mp_copy(&tmp, &first);
      mp_free(&first);
      mp_add(&first, &tmp, &inc); }

   return 0;
}

BUGS

GNU seq supports negative value and decimal point but mpseq doesn’t.

なんでこれを書いたか

seq では終わりの値を明示する必要があるため、無限列が出力できません。 では実用上無限に等しいくらいの多桁を指定したらどうだろうと考えました。 実際やってみたら上手く行かない場合があったのですが、 そういう自分はどうなのか？ 多桁やれるのか？ の確認のために書きました。 実務上は、多桁の扱えるライブラリや言語を使えば良いです。

確認用に使用した seq のバージョンは下記の通りです。

% seq --version
seq (GNU coreutils) 9.1
Copyright (C) 2022 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Ulrich Drepper.

バージョン表記内にもある通り、GNU seq は coreutils の一部ということも あり、GNU MP のようなライブラリは使わず libc 以外に依存していないよう です。

% ldd =seq
        linux-vdso.so.1 (0x00007fffc13fc000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f60d2e00000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f60d319f000)

手始めに小さい桁の数値を指定してみます。

% seq 10
1
2
3
4
5
6
7
8
9
10
% seq 10 12
10
11
12

問題なく表示されています。

上記のように、最初と最後の数値を指定するとその範囲だけを出力させること ができるので、この方法で大きな数値を少しだけ出力させてみます。

% seq 10000000000 10000000001
10000000000
10000000001
% seq 100000000000000000000 100000000000000000001
100000000000000000000
100000000000000000001
% seq 1000000000000000000000000000000 1000000000000000000000000000001
1000000000000000000000000000000
1000000000000000000000000000001

問題なさそうです。

% seq 10000000000000000000000000000000000000000 10000000000000000000000000000000000000001
10000000000000000000000000000000000000000
10000000000000000000000000000000000000001
% seq 100000000000000000000000000000000000000000000000000 100000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000
100000000000000000000000000000000000000000000000001
% seq 1000000000000000000000000000000000000000000000000000000000000 1000000000000000000000000000000000000000000000000000000000001
1000000000000000000000000000000000000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000001
% seq 10000000000000000000000000000000000000000000000000000000000000000000000 10000000000000000000000000000000000000000000000000000000000000000000001
10000000000000000000000000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000000000000000000000001
% seq 100000000000000000000000000000000000000000000000000000000000000000000000000000000 100000000000000000000000000000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000000000000000000000000000000
100000000000000000000000000000000000000000000000000000000000000000000000000000001
% seq 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
% seq 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

コマンドラインが画面幅を越えてしまうので、この辺で止めておきます。

なお、多桁の数値をコマンドラインから打ち込むのは大変なので、コマンドを 生成してくれるスクリプトを書きました（怠惰）。下記のような感じです。

% python3 -q
>>> from mpseqgen import mpseqgen as m
>>> m(0)
seq 1 1
>>> m(1)
seq 10 11
>>> m(3)
seq 1000 1001
>>> m(10)
seq 10000000000 10000000001
>>> m(2 * 10)
seq 100000000000000000000 100000000000000000001
>>>

seq にもう少し大きな値を渡してみましょう。

% python3 -q
>>> from mpseqgen import mpseqgen as m
>>> m(10**3)
seq 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
% seq 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 | head
1
2
3
4
5
6
7
8
9
10

1000桁の数値でも文句を言わず受け取ってくれました。 ここでは head コマンドを使って出力の先頭だけ表示しています。

seq コマンドに3つ引数を渡すことで、増分を指定することが出来ます。 間隔を2にしてみましょう。

% seq 10 2 20
10
12
14
16
18
20

同様に多桁でも試してみます。1000桁。

% seq 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
9999999999999999999731073176695623534282348575945525949258994493763287282024610367755114054811869631930666421916648220655294142520606968365335223871435017242762820794567970586973698890564071186428736691667173137634992770259851411773449256150524651659385141409430105973237502025611878801361748105745537491946144795418201484079582048538336970632673362947871910056282174622619551037453498446757329899442296892778338287437302901778820290426137049158991496035399937168855983519518959743163479471475079702696730977090171646435984524512014990041043419311272941414955013093059954497422734195248035971304504575538713459580498378850851688403171956722710850859505209579459709134510881049714360936717768295387965327621841742166516926409319653878520839067848988234948670550703227689191560316822918297610071014837999783821192315512185824993619969195605480907842303869071251516580867672072955240361703210592579426213980844789740009736221991632927085062431457550909271560663602154947063707982236377366647567795879936
12000000000000000000361053209699428777522454406909661353685252805484869004632626096316048772173718654311074641749763437417777529040814511168476182433626204597926303275900477704632603641572272087033941653306120787475763969484413515051180863971885507017692776718111548094060952917900386239463286823215826028134327511587623851087522013987569609762600322786208558982878099018061304342801479559484657728489746651565424390569465795700596359413180505747477083335029579462016043346676464296157001628619536260347503771961355971193339072221609765877494343957135526734816715304187894356361248370249623758921521638036800141947371518018695572336284485765822260072504304216306335832297290840216572656151974997862848981353353341499105140876667053694369856524007779375603934175882701714868639689015543589050520761087008710160557650382724269467307161705204577510939963553773207676876048548977385273398394375498694639123388993293978236108558863511858685518458206927279954017331672277104216426662568137262621612484591616
13999999999999999999281619748541532679803469948436221221675362584784140061732907687352203723536879936705795522958414722601699520520806681146432356526056932186562489951185702321631095960342006329340502556681285881532103555777496066021308080315106549809923894459804437899444527592273564482991852799883161969825125835042591042615403090082889136384046564502639540621125299736208449903506257113772330934639720459773964379589872905707342401145683845444244450403285084606703945365699687338248458128640391275219710068199665307275299512913225097143339666643978119462501668534025961816664844205371260063148248332059026848187310998692355590638201670562510571682758267050766250352873116679320435545359549091844506164567006813583481282380305780909856749873694086782095374013465104520948800789138064800694881649132495212562105805833009515253586357538608673060214625961255899194723711069657217844024209233435811532866267192932490901418164551509924827365633811638178566112661368171342019202633188686101984329349464064
16000000000000000000481404279599238370029939209212881804913670407313158672843501461754731696231624872414766188999684583223703372054419348224634909911501606130568404367867303606176804855429696116045255537741494383301018625979218020068241151962514009356923702290815397458747937223867181652617715764287768037512436682116831801450029351983426146350133763714944745310504132024081739123735306079312876971319662202087232520759287727600795145884240674329969444446706105949354724462235285728209335504826048347130005029281807961591118762962146354503325791942847368979755620405583859141814997826999498345228695517382400189263162024024927429781712647687763013430005738955075114443063054453622096874869299997150465308471137788665473521168889404925826475365343705834138578901176935619824852918687391452067361014782678280214076867176965692623076215606939436681253284738364276902501398065303180364531192500664926185497851991058637648144745151349144914024610942569706605356442229702805621902216757516350162149979455488
17999999999999999999401970818441342272310954750739441672903780186612429729943783052790886647594786154809487070208335868407625363534411518202591084003932333719204591043152528223175297174199430358351816441116659477357358212272300571038368368305735052149154820032508287264131511898240359896146281740955103979203235005571798992977910428078745672971580005431375726948751332742228884684440083633600550177469636010295772509779694837607541187616744014026736811514961611094042626481258508770300792004846903362002211325520117297673079203653761685769171114629689961707440573635421926602118593662121134649455422211404626895503101504698587448083629832484451325040259701789535028963638880292725959764076874091132122491684791260749849662672528132141313368715030013240630018738759338425905014018809912663711721902828164782615625022627250938409355411440343532230527947145846968420349060585983012935157007358602043079240730190697150313454350839347211055871786547280605217451771925597043424678187378065189524866844327936

これは少し誤差が出てしまうようです。桁を減らしてみます。100桁。

% seq 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
9999999999999999999669353532207342619498699019828496079271391541752018669482644324418977840117055488
11999999999999999999792937997655229997980417525632429563352467392978607903501420494941338279742537728
13999999999999999999916522463103117376462136031436363047433543244205197137520196665463698719368019968
15999999999999999999091538133518910482033961028049125190380631381050858870927736307793234800983146496
18000000000000000000163691393998892133425573043044230015595694946658375605557749006508419598618984448
19999999999999999999338707064414685238997398039656992158542783083504037338965288648837955680234110976

少し減らしましたがまだ誤差が出ています。桁をもっと減らしてみたら解消す るでしょうか？ まず20桁から10桁くらいを試してみます。

% python3 -q
>>> from mpseqgen import mpseqgen as m
>>> m(20)
seq 100000000000000000000 100000000000000000001
>>> m(16)
seq 10000000000000000 10000000000000001
>>> m(10)
seq 10000000000 10000000001
>>> 
% seq 100000000000000000000 20000000000000000000 200000000000000000000
100000000000000000000
120000000000000000000
140000000000000000000
160000000000000000000
180000000000000000000
200000000000000000000

20桁まで減らすと問題ないようです。16桁・10桁のテストはスキップします。 30桁付近だとどうでしょうか？

% python3 -q
>>> from mpseqgen import mpseqgen as m
>>> m(30)
seq 1000000000000000000000000000000 1000000000000000000000000000001
>>> m(32)
seq 100000000000000000000000000000000 100000000000000000000000000000001
>>> 
% seq 1000000000000000000000000000000 200000000000000000000000000000 2000000000000000000000000000000
1000000000000000000024696061952
1200000000000000000002147483648
1400000000000000000048318382080
1600000000000000000094489280512
1800000000000000000003221225472
1999999999999999999911953170432

30桁でだめなので少しずつ減らします。

% python3 -q
>>> from mpseqgen import mpseqgen as m
>>> m(28)
seq 10000000000000000000000000000 10000000000000000000000000001
>>> 
% seq 10000000000000000000000000000 2000000000000000000000000000 20000000000000000000000000000
9999999999999999999731564544
11999999999999999999463129088
13999999999999999999194693632
16000000000000000000000000000
17999999999999999999731564544
19999999999999999999463129088
% seq 1000000000000000000000000000 200000000000000000000000000 2000000000000000000000000000 
1000000000000000000000000000
1200000000000000000000000000
1400000000000000000000000000
1600000000000000000000000000
1800000000000000000000000000
2000000000000000000000000000

28桁と27桁の間が境界線のようです。 Python だったらこれくらいの桁は問題ないと思います……。

% python3 -q
>>> 10000000000000000000000000000 + 2000000000000000000000000000
12000000000000000000000000000
>>> n = 10000000000000000000000000000
>>> while n <= 20000000000000000000000000000:
...     print(n)
...     n += 2000000000000000000000000000
... 
10000000000000000000000000000
12000000000000000000000000000
14000000000000000000000000000
16000000000000000000000000000
18000000000000000000000000000
20000000000000000000000000000
% python3 -c 'print(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)'
20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
% python3 -c 'print(10**1000 + 2 * 10**999)'
12000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

1000 桁でも問題ないですね。

dc は任意精度の計算が出来る電卓プログラムです。 dc を使ったシェルスクリプトを書いてみました。

case $# in
1)
  a=1 ; b=1 ; c=$1 ;;
2)
  a=$1; b=1 ; c=$2 ;;
3)
  a=$1; b=$2; c=$3 ;;
*)
  usage; exit 1;
esac

while true
do
  echo $a
  a=$(dc -e "$a $b + p")
  t=$(dc -e "$c $a - p")
  case $t in (-*) exit 0 ;; esac
done

28桁の場合を seq コマンドと並べてみます。

% seq         10000000000000000000000000000 2000000000000000000000000000 20000000000000000000000000000
9999999999999999999731564544
11999999999999999999463129088
13999999999999999999194693632
16000000000000000000000000000
17999999999999999999731564544
19999999999999999999463129088
% sh mpseq.sh 10000000000000000000000000000 2000000000000000000000000000 20000000000000000000000000000  
10000000000000000000000000000
12000000000000000000000000000
14000000000000000000000000000
16000000000000000000000000000
18000000000000000000000000000
20000000000000000000000000000

ただし、上記のスクリプトに1000桁の数値を渡すと、下記のような見たことのな いエラーが出て上手く処理できませんでした。

dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: dc: value overflows simple integer; punting...
dc: input base must be a number between 2 and 16 (inclusive)
dc: dc: stack empty
dc: dc: dc: dc: dc: stack empty
dc: dc: dc: dc: dc: dc: dc: stack empty
dc: dc: stack empty

dc の高度な機能を使って下記のように書き直したら直ったのですが、 あまり理解せずに書いているのでスタックが溢れるおそれがあります。

case $# in
1)
  a=1 ; b=1 ; c=$1 ;;
2)
  a=$1; b=1 ; c=$2 ;;
3)
  a=$1; b=$2; c=$3 ;;
*)
  usage; exit 1;
esac

dc -e "[p $b+ d$c!<a]sa $a lax"

GNU seq は負数や小数を扱える優れた点もあります。 今回書いたプログラムではこれらは対応していません。

% seq 10 -1 7
10
9
8
7
% seq -5 -3
-5
-4
-3
% seq 7.5 10
7.5
8.5
9.5