INTERCHANGEABLE  FORMAT FOR MERSENNE NUMBERS RESIDUES

 

1.Introduction

Every day, the length of numbers being analyzed in GIMPS contest grows and grows, and so, the time needed to perform a Lucas-Lehmer test. A person can be tired of search, buy a new machine or change the client usually uses. In all cases, It would be nice an interchangeable format to avoid lost many CPU hours time.

Glucas program can use this format and so, the save files can be used by all platforms ( 32/64 bits, BIG-ENDIAN / LITTLE-ENDIAN)  with  two complement integer arithmetic. Read and write this kind of files is a bit slower than other formats (it cost about half a L-L iteration) but how often we read/write a save file ?.

What follows is a brief description of the format.
 
 

2.System compatibility requirements

The minimum requirements needed to read or write a save file with the proposed format are:

- Two-complement integer arithmetic.

- Unsigned integer types of 32 or 64 bits length.

- Unsigned 8-bits char or byte type.
 
 

3. The format.

The save file is divided into blocks of 8-bytes length.  Every block must be considered as a 64-bits  unsigned integer type.

    FORMAT OF A 8-BYTES BLOCK:

    byte 0:  bits 7-0 . First position in file (least significant byte)
    byte 1:  bits 8-15
    byte 2:  bits 16-23
    byte 3:  bits 14-31
    byte 4:  bits 32-39
    byte 5:  bits 40-47
    byte 6:  bits 48-55
    byte 7:  bits 56-63  last position in file (most significant byte)
 

The blocks are:
 

    BLOCK 0: bytes 1-8 .Format version
    This is reserved to identify the file as a Interchangeble Merssene Residue File Format.
    bytes 0-4: The signature 0x006A64B1. Is the exadecimal representation of 6972593 (the last known Mersenne prime exponent).
    bytes 4-7: the version. This is version 2. So 0x00000002
 
 

    BLOCK 1: bytes 9-16 .Program identification
    This is reserved to identify the program and version which generate the file. As an orientation, the proposal is:
    byte 0: the program:
        Example. Byte 2 of block 0 can be, in hexadecimal
                      0x11 for prime95/mprime
                      0x22 for Mlucas
                      0x33 for Glucas
                      .......
    bytes 1-3: the version. Every program should use this three bytes in his own format.
    byte 4: What the residue is:
        0 : Lucas-Lehmer test residue.
        1 : p-1 residue.
        2 : A general mersenne residue, (example : a residue in a ECM factorization).
    bytes 5-7: at the moment set two 0. Reserved for future uses.

    BLOCK 2: bytes 17-24. Exponent.
    This is the block changed from version 1. In version 1 it was the exponent all the block. Now the upper half has other information.

        Bytes 0-3: The exponent of the Mersenne number, e.g, 657849 for M657849. Unsigned integer format.

    Bytes 4-7: The optional shift account. To get the proper residue, it have to be rotate to rigth this number of bits. In a non rotated version is set to 0.

    BLOCK 3: bytes 25-32. The FFT-length used, if any.
    An integer indicating the FFT run-length, in size_of_reals, used to compute the residue saved.   Actually, it is only an informative data, every binary can continue the work with a FFT-runlenght according to their own accuracy capabilities.

    BLOCK 4: bytes 33-40. Iteration / B1 LIMIT.
    In a L-L test: The iteration of the Lucas-Lehmer test saved. This is important to unify:
        4 would be the iteration 0
        14 would be the iteration 1
        .....

    If the starting point L(0) is not 4, like prime95 does, the residue should be rotated according  with the number of bits readed in block 2. Once rotated L(0)=4, L(1)=14 and so on.
    In a P-1 factorization must be the B1 limit.

    For other uses is undefined.

    Block 5: bytes 41-48. Round off Error
    In a L-L test: the round off error of iteration being saved. Because of we need to store it in a integer format, the error is transformed according to:

    error_saved := (unsigned int) (fabs(frac_roundoff_error) * 1000000.0)

    In other kinds of residues it is yet undefined. (may be a B2 limit)
 

    Blocks 6 to (5+N): bytes 49 to (N*8+48): The residue
    This part contains the residue. It is stored in compact two-complement integer form, using all the blocks needed to store the 'q' bits of the Mersenne Number Mq. The needed N blocks can be easily computed by
    N := floor ( (q-1)/64 + 1)

    The unused bits (if any) in the last block must be filled by zeroes. The first block of residue (first on file) will contain bits 0-63, the second 64-127 and so on.

    Block 6+N: bytes N*8+49 to N*8+56: The last carry.
    In the normalization process from the float array in DWT to the compact integer form, one must play with a carry propagation. After the last float DWT array element has been transformed, it remains a 'last carry' one need to add to the residue (usually only to the first bits). If the write routines already has written the first residue blocks (to save memory) this blocks should need to be readed again. To avoid this problem, this block contain the last carry.

    NOTE: The last carry, if no zero, usually is -1, so all the bits are zeroes or ones.

    Glucas add the last carry to the residue before writing, so this block always is zero.

    Block 7+N: bytes N*8+57 to N*8+64: The sum check control.
    This block contains the sum of the previous blocks mod(2^32 - 1). It is easy and fast to compute with both 32 and 64 bits scheme.
 

    Blocks 8+N to the end of file: UNDEFINED YET
    More blocks can be added at the end of the file. This part of file can be used for proposes like a brief history of the machines/users and errors from the beginning of work to the actual state.