Phrot announcements

[mdettweiler]

Originally Posted by rogue

If using 0.51 with a patched version of YEAFFT, no. There have been no new patches to YEAFFT.

Ah, I see.

So, which versions does the bug affect?

[rogue]

Originally Posted by mdettweiler

Ah, I see.

So, which versions does the bug affect?

Anything after 0.52.

So far, from my testing, the probability of an FFT rounding error for bases that are not powers of 2 is about 4%.

[Shaopu Lin]

The package phrot_070.zip downloaded from http://home.roadrunner.com/~mrodenkirch/phrot_070.zip is damaged and lose some necessary files to compile due to this damage.

math@linux-0rdr:~/Desktop/other/test/temp> unzip phrot_070.zip
Archive:  phrot_070.zip
error [phrot_070.zip]:  missing 12939 bytes in zipfile
  (attempting to process anyway)
retry - request = 0x18446744073709538677
error [phrot_070.zip]:  attempt to seek before beginning of zipfile
  (please check that you have transferred or created the zipfile in the
  appropriate BINARY mode and that you have compiled UnZip properly)
  (attempting to re-compensate)
file #1:  bad zipfile offset (local header sig):  0
  (attempting to re-compensate)
error [phrot_070.zip]:  attempt to seek before beginning of zipfile
  (please check that you have transferred or created the zipfile in the
  appropriate BINARY mode and that you have compiled UnZip properly)
retry - request = 0x18446744073709539484
error [phrot_070.zip]:  attempt to seek before beginning of zipfile
  (please check that you have transferred or created the zipfile in the
  appropriate BINARY mode and that you have compiled UnZip properly)
retry - request = 0x18446744073709543826
error [phrot_070.zip]:  attempt to seek before beginning of zipfile
  (please check that you have transferred or created the zipfile in the
  appropriate BINARY mode and that you have compiled UnZip properly)
  inflating: phrot/makefile          
  inflating: phrot/mathtypes.h       
  inflating: phrot/phrot.c           
  inflating: phrot/phrot.p3          
  inflating: phrot/readme_phrot.txt  
  inflating: phrot/reduce.h          
   creating: phrot/testm/
  inflating: phrot/testm/abcm.in     
   creating: phrot/testp/
  inflating: phrot/testp/abcp.in     
  inflating: phrot/x86.h             
math@linux-0rdr:~/Desktop/other/test/temp>

[rogue]

Originally Posted by Shaopu Lin

The package phrot_070.zip downloaded from http://home.roadrunner.com/~mrodenkirch/phrot_070.zip is damaged and lose some necessary files to compile due to this damage.

I am aware of the problem, which is why I haven't posted the announcement yet. I'll fix it later today.

[mdettweiler]

Quick question: does the incorrect-residual bug affect Phrot 0.69 also, or just versions from 0.52-0.68?

[rogue]

Originally Posted by mdettweiler

Quick question: does the incorrect-residual bug affect Phrot 0.69 also, or just versions from 0.52-0.68?

0.69 should work correctly. I know that Geoff ran through many tests that would have uncovered the bug if it were still in the code.

[rogue]

Here are the changes from 0.68 to 0.69:

• Default to always error checking as phrot can exhibit rounding errors for all bases.
• Added -n switch to disable error checking with a caveat (see above). Modified use of -a switch.
• Added a test suite of PRP numbers to be tested with phrot release.

and from 0.69 to 0.70:

• Allow b and n to be unsigned, but limit b to 5 million. Even with such high b, some tests will encounter the FFT rouding error.
• Limit k to 2^54 on x86 and 2^44 on non-x86. It is possible that other large k will cause problems, but testing so far has not indicated that this change is safe are larger k do seem to test without a problem.

You can download the latest sources and a Windows build from here.

I have a note regarding the FFT rounding errors. I know for a fact that bases 2, 3, and 10 (and their powers) will have FFT rounding errors. I have not seen the issue with any other bases. That does not mean that other bases do not exhibit the errors, only that I haven't the time to run thousands of tests for various k/b combinations to see which have problems. I recommend that anyone using phrot to run 1000 tests for small n for each k and b combination that they are testing. If no FFT rounding errors occur, then you are probably safe to use the -n option (although I won't guarantee it), which will disable the error checking.

[gd_barnes]

Max,

You are correct that I am using Phrot version 0.51 that you loaded on my machines. I didn't do anything special with the error checking or -e switch (which I assume means error checking is on). By that I mean I didn't test using the -e switch.

Therefore, should my tests for bases 22 and 28 be OK?

This is the most unfortunate for Cruelty on base 10, who has run far more tests for that base than I have for my 2 bases.

Cruelty, if you happen to read this, since you are rerunning your tests for base 10 using LLR, can you compare the residues between the LLR and Phrot runs? It might help quite a bit if we knew which tests, if any, came up with incorrect residues on Phrot. Also, can you state which version of Phrot you are using? Thanks.


Gary

[mdettweiler]

Originally Posted by gd_barnes

Therefore, should my tests for bases 22 and 28 be OK?

Yes. Version 0.51 is not affected by the issue.

[Cruelty]

Originally Posted by gd_barnes

Cruelty, if you happen to read this, since you are rerunning your tests for base 10 using LLR, can you compare the residues between the LLR and Phrot runs? It might help quite a bit if we knew which tests, if any, came up with incorrect residues on Phrot. Also, can you state which version of Phrot you are using? Thanks.

I have been using versions 0.62, 0.65, 0.67, 0.68, 0.681, and I am planning to verify those residues with LLR ones just as I did lately with 2*3^n-1 search...

[rogue]

Here are the changes from:

• Removed default for always error checking. Phrot now checks the first 30 and last 30 iterations of all tests as well as every 64th iteration of each test. With this change, all tests in the test suite now produce correct results, at least on PPC and Core 2 Duo.
• Phrot now keeps track of total time spent on a test, so that if stopped and restarted, the time for the test will now represent the total time spent on a test, not just the time since phrot was started.

You can download the latest sources and a Windows build from here.

Based upon all of my testing (weeks worth of testing), this version correctly detected all FFT rounding errors for the tests I performed. Due to this, I am now removing the mandatory error checking, which means that phrot will regain about 10-20% of the speed it lost in 0.70. I will eventually modify the PRPNet client to not pass the -e flag.