Re: [math-fun] Add or subtract the result. Iterate.

17 Oct 2012

      I've looked at the flight of 13094, and it's relentless - up to 115000 digits after 83M iterations, and still growing...

83125533[115146]: 143524455825705033056031082470820829609344558479726770660582324880706594479267893056859434808342457255[...]

If anyone's interested, this is what I wrote last night to investigate so deeply. It deliberately logs very little, as it can continue from where it left off trivially, only recording at most one log per milliard digits of computation, and then only recording a new log when a new maximum length is reached. On a 12-year-old machine, that's still a log every 20 seconds. 

Phil
-- 8< --
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>

//#define DEBUG

void rprint(int len, const uint8_t *restrict src)
{
    while(len-->0) {
        putchar('0'+src[len]);
    }
}

int maywesub(int len, const uint8_t * restrict src)
{
    uint8_t prev2=src[--len]*2; // top digit
    while(len-->0) {
        uint8_t this=src[len];
        if(this==0 || this==prev2) { prev2=2*this; continue; }
        if(this<prev2) { return 1; }
        return 0;
    } 
    return 1;
}

int suminto(int len, uint8_t * restrict src)
{
    int carry=0;
    uint8_t prev=src[len-1];
    for(int i=0; i<len; ++i) {
        uint_fast8_t diff = (src[i]>=prev) ? src[i]-prev : prev-src[i];
        uint_fast8_t sum=src[i]+diff+carry;
      //uint_fast8_t sum = (src[i]>=prev) ? src[i]+src[i]+carry-prev : prev+carry;
        prev=src[i];
        if(sum>=10) { src[i]=sum-10; carry=1; }
        else { src[i]=sum; carry=0; }
    }
    if(carry) { src[len++]=carry; }
#if defined(DEBUG)
    printf("sum to ");
    rprint(len, src);
    printf("\n");
#endif
    return len;
}

int subinto(int len, uint8_t * restrict src)
{
    int borrow=0;
    uint8_t prev=src[len-1];
    for(int i=0; i<len; ++i) {
       uint_fast8_t diff = (src[i]>=prev) ? src[i]-prev : prev-src[i];
       int sub=src[i]-(diff+borrow); // borrow forces this to be done as int
       //int sub = (src[i]>=prev) ? prev-borrow : src[i]+src[i]-prev-borrow; // borrow forces this to be done as int
        prev=src[i];
        if(sub<0) { src[i]=sub+10; borrow=1; }
        else { src[i]=sub; borrow=0; }
    }
    assert(!borrow);
    while(src[len-1]==0) { --len; }
#if defined(DEBUG)
    printf("sub to ");
    rprint(len, src);
    printf("\n");
#endif
    return len;
}

void dump(int iter, int len, const uint8_t * restrict src, const char * restrict msg)
{
    printf("%i[%i]: ", iter, len);
    rprint(len, src);
    printf("%s\n", msg);
}

int main(int argc, char**argv)
{
    int iter=0;
    if(argc>2) {
        iter=strtoul(argv[1],0,0);
        --argc; ++argv;
    }
    int len=strlen(argv[1]);
    int buflen=(len|0x3f)+1;
    int maxlen=len;
    uint8_t *buf;
    buf=malloc(buflen);
    for(int i=0; i<len; ++i) { buf[i]=argv[1][len-1-i]-'0'; }
    int printflag=0;
    int work=0;
    while(1) {
        ++iter;
        int sub=maywesub(len, buf);
        if(!sub) {
            len=suminto(len, buf);
            if(len>=maxlen) {
                if(printflag) {
                    dump(iter, len, buf, "");
                    printflag=0;
                    work=0;
                }
                maxlen=len;
            }

            if(len>=buflen) {
                buflen=(len|0x3f)+1;
               //printf("realloc(%i)\n", buflen);
                buf=realloc(buf,buflen);
            }
        } else {
            len=subinto(len, buf);
        }
#if defined(DEBUG)
        printf("%i: len=%i\n", iter, len);
#else
        if((work+=len)>1000000000) {
            work=0;
            printflag++;
        }
#endif

        if(iter>100 && len<3) {
            dump(iter, len, buf, "\naborting, assuming it will loop");
            break;
        }
    }
}

Re: [math-fun] Add or subtract the result. Iterate.

Phil Carmody