start
Differences
This shows you the differences between two versions of the page.
| start [2024/02/18 14:41] – [updated on 2024.02.17] mino | start [2025/08/15 14:08] (current) – external edit 127.0.0.1 | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ===== The number of magic squares of order six counted up to rotations and reflections. ===== | + | __[[magicsquare6-j|Move to the Japanese page]]__ |
| + | |||
| + | ===== The number of magic squares of order six counted up to rotations and reflections ===== | ||
| <file - nms6.txt> | <file - nms6.txt> | ||
| - | 17 753 889 197 660 635 632 updated | + | 17 753 889 197 660 635 632 |
| - | (17 753 889 189 701 385 264 updated | + | |
| - | (17 753 889 189 701 384 304 reported on 2023.07.18.) | + | |
| </ | </ | ||
| - | This result is consistent with stochastic estimates 1.7745(16)·10< | + | [[https:// |
| - | Using hundreds of GPUs at cloud resource rental services, it took about six months to complete the counting, | + | This number has been confirmed by completing the enumeration twice using hundreds of GPUs provided |
| - | Because of the extraordinary volume | + | As the result |
| + | obtained in July 2023 was found to be incorrect. More details | ||
| + | The result is consistent with stochastic estimates 1.8(2)・10< | ||
| + | |||
| + | - Y. Ohishi, in Japanese, Estimation of number of solutions of 6th order magic square by random sampling, Sugei Puzzle No.177, April 1992 | ||
| - K. Pinn and C. Wieczerkowski, | - K. Pinn and C. Wieczerkowski, | ||
| - W. Trump, [[https:// | - W. Trump, [[https:// | ||
| Line 17: | Line 21: | ||
| - | ===== Errors found ===== | + | ===== Correction history |
| - | ==== updated on 2024.02.17 ==== | + | More than a thousand of instances of GPU server were used in the enumeration and some of them were unfortunately faulty and produced wrong results. To find and correct such errors, every subtotal was calculated at least twice and extra counting was done to determine the correct answer when a mismatch happened. There were following two cases where the initial result was incorrect. |
| - | Another erroneous instance was found. It ran with an RTX-4090 for about one month and produced about 19,000 sub-subtotals. Out of those sub-subtotals 6 were incorrect. All of the incorrect results were produced in the last one hour of the lifetime of the instance. After the erroneous behavior, the GPU of the instance became unusable with an error message of " | + | ==== corrected on 2023.09.07 ==== |
| - | As the result of the correction, the number increased by 7 959 250 368 (331 635 432 x24). | + | During the thorough double-check, |
| - | + | ||
| - | ==== updated on 2023.09.07 ==== | + | |
| - | During the thorough double-check, | + | |
| As the result of the correction, the number increased by 960(40x24). | As the result of the correction, the number increased by 960(40x24). | ||
| - | While these errors have not damaged my confidence in the logic and the code used in the calculation, | + | ==== corrected on 2024.02.17 ==== |
| + | |||
| + | Another erroneous instance was found. It ran with an RTX-4090 for about one month and produced about 19,000 sub-subtotals. Out of those sub-subtotals, | ||
| + | |||
| + | As the result of the correction, the number increased by 7 959 250 368 (331 635 432 x24). | ||
| + | |||
| - | ===== Code corrected (2023.11.30) ===== | ||
| - | The code used in the initial enumeration was discovered to contain a mistake related to GPU thread synchronization. A corrected version of the code is currently running for the thorough double-check. No discrepancy due to the mistake has been found so far. | ||
| ===== Subsets and subtotals ===== | ===== Subsets and subtotals ===== | ||
| Line 41: | Line 46: | ||
| * [[Defintion of subsets|Definition of subsets]] | * [[Defintion of subsets|Definition of subsets]] | ||
| - | * [[subtotals|List of 4,329 subtotals]] 3 of subtotals are known to be incorrect, but are kept uncorrected intentionally. | + | * [[subtotals|List of 4,329 subtotals]] |
| - | * [[https:// | + | * (3 of subtotals are known to be incorrect, but are kept uncorrected intentionally.) |
| - | | + | * [[https:// |
| + | * (18 of sub-subtoals are known to be incorrect, but are kept uncorrected intentionally.) | ||
| + | | ||
| [[strategies|Strategies in counting magic squares]] | [[strategies|Strategies in counting magic squares]] | ||
| - | [[ms-20231201.cu|CUDA code]] (corrected on 2023.11.28 and updated on 2023.12.01) | + | [[ms-20240504.cu|CUDA code]] (corrected on 2023.11.28 and updated on 2024.05.04) |
| - | * Counts magic squares of an order 3..6 up to [[https:// | + | * Counts magic squares of an order from 3 to 6 up to [[https:// |
| - | * Runs at a typical speed of 3.7G counts/sec on Nvidia GeForce RTX-4090 for order 6. | + | * Runs at a typical speed of 3.8G counts/ |
| * Nvidia GPU of Pascal architecture (sm_60) or newer is assumed. | * Nvidia GPU of Pascal architecture (sm_60) or newer is assumed. | ||
| * Multi GPU systems are supported. **[[https:// | * Multi GPU systems are supported. **[[https:// | ||
| Line 60: | Line 67: | ||
| * '' | * '' | ||
| * The code doesn' | * The code doesn' | ||
| + | |||
| + | *The code was corrected on 2023.11.28.\\ The code used in the initial enumeration was discovered to contain a mistake related to GPU thread synchronization. Corrected versions of the code were used in the second enumeration. No erroneous result caused by this mistake was found. | ||
| [[ms-20230918-m.c|Non-CUDA code in C using pthread]] (updated on 2023.09.18) | [[ms-20230918-m.c|Non-CUDA code in C using pthread]] (updated on 2023.09.18) | ||
| Line 67: | Line 76: | ||
| * Much slower than the CUDA code, but easier to read. | * Much slower than the CUDA code, but easier to read. | ||
| + | ===== Semi-magic squares ===== | ||
| + | |||
| + | The latest code used in the second enumeration counted semi-magic squares besides magic squares and produced the same result as discovered by a very different approach of A. Ripatti[5]. This match is considered as a cross verification of the counting method and of computing resources used in the calculation. All [[semi_magic_subtotals|subtotals of semi-magic (including magic) squares]] are available. | ||
| + | |||
| + | * 5. A. Ripatti, On the number of semi-magic squares of order 6, arXiv: | ||
| + | |||
| + | ===== Acknowledgments ===== | ||
| + | |||
| + | I would like to thank Walter Trump for his discussion, suggestion, and encouragement. He reviewed my method and verified a part of my result using his own code. He suggested me to count semi-magic squares in the second enumeration and encouraged me to complete my work. Visit his website [[https:// | ||
| ===== Time stamps ===== | ===== Time stamps ===== | ||
| - | * CUDA code: 2023.12.01 version [[https:// | + | |
| + | | ||
| * pthread code: 2023.09.18 version [[https:// | * pthread code: 2023.09.18 version [[https:// | ||
| * [[https:// | * [[https:// | ||
| --------------------------------- | --------------------------------- | ||
| - | 2024/ | ||
| --- // | --- // | ||
| Professor emeritus, University of Yamanashi, Japan | Professor emeritus, University of Yamanashi, Japan | ||
start.1708234868.txt.gz · Last modified: 2024/02/18 14:41 by mino