[Python-checkins] r86319 - python/branches/py3k-cdecimal/Modules/cdecimal/transpose3.c

stefan.krah python-checkins at python.org
Mon Nov 8 15:17:48 CET 2010


Author: stefan.krah
Date: Mon Nov  8 15:17:48 2010
New Revision: 86319

Log:
These matrices are not used in the number theoretic transform.



Removed:
   python/branches/py3k-cdecimal/Modules/cdecimal/transpose3.c

Deleted: python/branches/py3k-cdecimal/Modules/cdecimal/transpose3.c
==============================================================================
--- python/branches/py3k-cdecimal/Modules/cdecimal/transpose3.c	Mon Nov  8 15:17:48 2010
+++ (empty file)
@@ -1,519 +0,0 @@
-/*
- * Copyright (c) 2008-2010 Stefan Krah. All Rights Reserved.
- * Licensed to PSF under a Contributor Agreement.
- */
-
-
-#include "mpdecimal.h"
-#include <stdlib.h>
-#include <string.h>
-#include <limits.h>
-#include <assert.h>
-#include "bits.h"
-#include "constants.h"
-#include "typearith.h"
-#include "transpose.h"
-
-
-/*
- * In situ transposition of a 3 x 2^n or 2^n x 3 matrix. For efficient memory
- * access, we split the transposition into two steps. In the 3 x 2^n case, we
- * first perform a block matrix transpose on blocks of size BMEMB followed by
- * a series of 3 x BMEMB transposes. Example with BMEMB = 4:
- *
- *   Input 3 x 2 block matrix:
- *
- *         0   1   2   3    4   5   6   7
- *         8   9  10  11   12  13  14  15
- *        16  17  18  19   20  21  22  23
- *
- *   After the block transpose:
- *
- *        0   1   2   3    8   9  10  11   16  17  18  19
- *        4   5   6   7   12  13  14  15   20  21  22  23
- *
- *   After performing two 3 x BMEMB transpositions:
- *
- *        0   8  16
- *        1   9  17
- *        2  10  18
- *        (...)
- *
- * In the 2^n x 3 case, we simply do the steps in reverse order.
- *
- * For efficient in-place block transposition, we swap the blocks cyclically.
- * The starting points of the distinct cycles are precalculated. The arrays
- * below contain the block numbers, which have to be multiplied by BMEMB to
- * get the actual addresses. In an m x n block matrix, the next block number t
- * as a function of the current block number s is calculated by:
- *
- *    t = m*s % (m*n - 1)
- *
- * The inverse of the transpose is:
- *
- *    t = n*s % (m*n - 1)
- *
- * (This does not apply to the last block, which is not moved anyway.)
- *    
- */
- 
-
-/* Cycle start points */
-static const mpd_size_t c0[] = {MPD_SIZE_MAX};              /* 2^0 blocks */
-static const mpd_size_t c1[] = {1, MPD_SIZE_MAX};           /* 2^1 blocks */
-static const mpd_size_t c2[] = {1, 2, MPD_SIZE_MAX};        /* 2^2 blocks */
-static const mpd_size_t c3[] = {1, 5, MPD_SIZE_MAX};        /* (...)      */
-static const mpd_size_t c4[] = {1, 5, MPD_SIZE_MAX};
-static const mpd_size_t c5[] = {1, 5, 7, 19, MPD_SIZE_MAX};
-static const mpd_size_t c6[] = {1, 7, MPD_SIZE_MAX};
-static const mpd_size_t c7[] = {1, 5, MPD_SIZE_MAX};
-static const mpd_size_t c8[] = {
-  1, 2, 4, 5, 7, 8, 10, 13, 14, 26, 59, 118, 236, 413, MPD_SIZE_MAX
-};
-static const mpd_size_t c9[] = {
-  1, 2, 4, 5, 7, 10, 11, 13, 14, 17, 20, 22, 23, 25, 28, 34, 35, 37, 46, 50,
-  53, 68, 70, 74, 92, 100, 140, 307, MPD_SIZE_MAX
-};
-static const mpd_size_t c10[] = {1, 2, 17, 34, 37, 74, 83, 166, MPD_SIZE_MAX};
-static const mpd_size_t c11[] = {1, 5, MPD_SIZE_MAX};
-static const mpd_size_t c12[] = {
-  1, 2, 4, 5, 7, 8, 11, 13, 14, 16, 17, 22, 25, 26, 32, 35, 41, 44, 49, 52,
-  53, 55, 61, 65, 77, 82, 88, 103, 104, 154, 164, 176, 275, 352, 385, 539,
-  1117, 2234, MPD_SIZE_MAX
-};
-static const mpd_size_t c13[] = {1, 5, 11, 25, 55, 125, 983, 4915, MPD_SIZE_MAX};
-static const mpd_size_t c14[] = {
-  1, 2, 5, 7, 10, 13, 14, 23, 26, 46, 115, 230, 2137, 10685, MPD_SIZE_MAX
-};
-static const mpd_size_t c15[] = {1, 5, 11, 17, 23, 31, 197, 499, 985, 2167, MPD_SIZE_MAX};
-static const mpd_size_t c16[] = {
-  1, 2, 4, 5, 8, 10, 11, 22, 421, 467, 842, 934, 1868, 3736, MPD_SIZE_MAX
-};
-static const mpd_size_t c17[] = {
-  1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31,
-  32, 34, 38, 40, 41, 43, 44, 46, 47, 50, 52, 53, 55, 56, 58, 59, 62, 64, 65,
-  67, 68, 71, 73, 76, 77, 80, 82, 83, 85, 86, 88, 91, 92, 94, 95, 97, 100, 103,
-  106, 110, 112, 115, 116, 118, 121, 128, 130, 134, 136, 137, 143, 146, 149,
-  152, 155, 160, 161, 163, 166, 170, 176, 181, 187, 190, 194, 197, 200, 205,
-  206, 209, 215, 221, 224, 227, 230, 232, 235, 251, 256, 263, 265, 272, 274,
-  275, 277, 287, 295, 304, 310, 311, 320, 322, 326, 335, 337, 340, 341, 359,
-  365, 380, 388, 410, 412, 442, 460, 470, 485, 502, 515, 530, 544, 548, 550,
-  571, 575, 577, 589, 605, 613, 622, 644, 680, 685, 691, 715, 730, 745, 905,
-  935, 970, 1226, 1795, 78643, MPD_SIZE_MAX
-};
-static const mpd_size_t c18[] = {1, 7, MPD_SIZE_MAX};
-static const mpd_size_t c19[] = {1, 5, 7, 13, 71, 355, 22153, 155071, MPD_SIZE_MAX};
-static const mpd_size_t c20[] = {
-  1, 2, 4, 5, 7, 8, 10, 13, 14, 26, 241979, 483958, 967916, 1693853, MPD_SIZE_MAX
-};
-static const mpd_size_t c21[] = {1, 2, 4, 5, 7, 10, 14, 19, 20, 1258291, MPD_SIZE_MAX};
-static const mpd_size_t c22[] = {
-  1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31,
-  32, 34, 35, 37, 38, 40, 41, 43, 46, 47, 49, 50, 52, 56, 58, 61, 62, 64, 67,
-  68, 70, 71, 73, 74, 76, 77, 79, 82, 83, 85, 86, 92, 94, 95, 97, 98, 100, 101,
-  103, 104, 107, 109, 112, 113, 115, 116, 119, 121, 122, 124, 127, 128, 131,
-  133, 136, 139, 140, 142, 143, 145, 146, 148, 149, 151, 152, 154, 155, 157,
-  161, 163, 164, 166, 169, 172, 173, 179, 181, 184, 187, 190, 196, 197, 200,
-  202, 205, 206, 208, 209, 214, 215, 217, 218, 223, 224, 229, 230, 232, 233,
-  239, 241, 245, 248, 253, 257, 263, 266, 269, 272, 278, 280, 281, 283, 284,
-  286, 289, 302, 304, 314, 319, 322, 323, 328, 329, 335, 338, 344, 346, 349,
-  355, 358, 359, 365, 368, 373, 374, 377, 379, 380, 389, 392, 394, 407, 409,
-  410, 416, 418, 425, 430, 431, 433, 436, 437, 448, 451, 457, 458, 460, 463,
-  464, 466, 473, 478, 482, 485, 490, 496, 505, 511, 521, 526, 532, 533, 541,
-  544, 556, 557, 559, 562, 566, 568, 569, 589, 593, 604, 646, 676, 679, 697,
-  703, 713, 716, 743, 746, 749, 784, 799, 814, 815, 827, 832, 865, 866, 871,
-  877, 893, 902, 913, 916, 946, 1031, 1039, 1075, 1079, 1114, 1127, 1292, 1387,
-  1445, 1463, 1723, 2299, 103991, 207982, 415964, 519955, 727937, 831928,
-  1039910, 1143901, 1351883, 1663856, 1767847, 1975829, 2079820, 2287802,
-  2599775, 2703766, 3223721, 3535694, 3639685, 3951658, 4159640, 6343451,
-  6967397, 7903316, MPD_SIZE_MAX
-};
-static const mpd_size_t c23[] = {
-  1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 43, 47, 49, 59, 61, 65, 67,
-  71, 77, 83, 85, 95, 97, 101, 103, 107, 113, 119, 125, 133, 145, 151, 163, 175,
-  179, 185, 187, 199, 203, 209, 217, 221, 229, 239, 247, 269, 281, 289, 319,
-  341, 377, 413, 421, 475, 479, 493, 551, 587, 703, 725, 841, 1421, 1463, 1885,
-  1943, 2407, 2755, 45673, 502403, 867787, 1324517, MPD_SIZE_MAX
-};
-static const mpd_size_t c24[] = {
-  1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31,
-  32, 34, 35, 37, 38, 40, 41, 43, 44, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61,
-  62, 65, 67, 68, 70, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 88, 89, 91, 94,
-  95, 97, 98, 100, 101, 103, 106, 107, 109, 112, 113, 115, 116, 118, 119, 121,
-  122, 124, 125, 130, 133, 136, 137, 140, 142, 143, 146, 148, 149, 151, 152,
-  160, 161, 164, 166, 167, 169, 170, 172, 173, 175, 176, 178, 179, 181, 187,
-  188, 190, 191, 193, 194, 196, 197, 199, 200, 202, 203, 211, 212, 214, 215,
-  217, 221, 223, 224, 226, 229, 232, 235, 238, 241, 242, 244, 247, 250, 253,
-  259, 260, 263, 265, 266, 269, 272, 274, 275, 277, 280, 281, 283, 284, 286,
-  287, 292, 293, 295, 296, 298, 301, 302, 304, 305, 307, 313, 317, 328, 329,
-  332, 334, 335, 337, 338, 340, 341, 343, 346, 347, 352, 353, 356, 361, 362,
-  365, 367, 373, 374, 376, 377, 379, 380, 382, 386, 388, 391, 392, 394, 398,
-  400, 401, 406, 419, 422, 424, 425, 428, 430, 433, 434, 437, 442, 445, 446,
-  449, 452, 455, 458, 461, 463, 467, 470, 475, 476, 479, 482, 487, 488, 494,
-  497, 503, 505, 511, 515, 517, 518, 523, 526, 529, 530, 532, 538, 544, 547,
-  548, 551, 557, 560, 565, 566, 568, 569, 571, 572, 575, 577, 581, 583, 587,
-  589, 590, 593, 595, 596, 602, 604, 610, 613, 614, 619, 623, 634, 643, 647,
-  649, 664, 668, 674, 689, 691, 692, 694, 706, 707, 719, 721, 722, 727, 730,
-  733, 737, 745, 748, 754, 760, 764, 767, 776, 781, 787, 788, 791, 800, 805,
-  821, 823, 833, 835, 838, 844, 845, 848, 850, 856, 868, 875, 881, 883, 884,
-  890, 892, 893, 899, 904, 905, 907, 916, 926, 931, 949, 964, 976, 979, 989,
-  991, 995, 1010, 1019, 1022, 1036, 1043, 1046, 1055, 1064, 1073, 1075, 1091,
-  1094, 1102, 1114, 1115, 1136, 1138, 1142, 1147, 1166, 1174, 1186, 1190, 1204,
-  1211, 1219, 1220, 1238, 1246, 1273, 1279, 1297, 1298, 1301, 1315, 1325, 1327,
-  1378, 1388, 1405, 1414, 1451, 1459, 1483, 1490, 1501, 1519, 1531, 1543, 1562,
-  1574, 1633, 1646, 1676, 1690, 1709, 1814, 1862, 1867, 2021, 2128, 2171, 2219,
-  2267, 2332, 2348, 2491, 2558, 2657, 2971, 3127, 3191, 3211, 3724, 3829, 4079,
-  6563, 7669, 13126, 15338, 26252, 32815, 38345, 52504, 53683, 65630, 72193,
-  76690, 84359, 99697, 105008, 107366, 130373, 131260, 144386, 168718, 176387,
-  191725, 199394, 203453, 222401, 260746, 283753, 288772, 314429, 329767,
-  375781, 406457, 421795, 444802, 452471, 498485, 544499, 605851, 651865,
-  659534, 682541, 751562, 904942, 1234709, 1510793, 1648835, MPD_SIZE_MAX
-};
-static const mpd_size_t c25[] = {
-  1, 5, 7, 11, 13, 17, 23, 25, 31, 49, 67, 115, 161, 253, 391, 875333, 4376665,
-  6127331, 20132659, 21883325, MPD_SIZE_MAX
-};
-static const mpd_size_t c26[] = {
-  1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31,
-  32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59,
-  61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 88, 89, 91,
-  92, 94, 97, 98, 100, 101, 103, 104, 106, 107, 109, 110, 112, 113, 115, 118,
-  121, 122, 124, 125, 128, 130, 131, 133, 134, 136, 137, 139, 140, 142, 143,
-  145, 146, 151, 152, 154, 155, 157, 158, 160, 161, 163, 164, 167, 169, 173,
-  175, 176, 178, 179, 181, 184, 185, 187, 193, 194, 197, 199, 200, 202, 203,
-  205, 206, 208, 209, 211, 212, 214, 215, 217, 218, 220, 221, 223, 224, 226,
-  227, 229, 230, 233, 236, 241, 242, 244, 245, 247, 248, 250, 251, 253, 256,
-  257, 259, 260, 262, 263, 265, 266, 268, 271, 272, 274, 278, 280, 281, 283,
-  284, 286, 287, 289, 290, 292, 295, 301, 302, 304, 305, 307, 310, 313, 314,
-  316, 317, 319, 320, 322, 323, 326, 328, 329, 335, 337, 338, 346, 347, 349,
-  350, 352, 353, 356, 358, 361, 362, 367, 368, 370, 371, 373, 377, 383, 385,
-  386, 391, 394, 395, 397, 398, 400, 401, 403, 404, 406, 407, 409, 410, 412,
-  413, 416, 418, 419, 421, 422, 424, 428, 431, 433, 434, 436, 437, 440, 442,
-  445, 446, 448, 449, 451, 452, 454, 455, 458, 460, 463, 466, 467, 469, 472,
-  473, 481, 482, 484, 485, 488, 490, 491, 493, 494, 496, 500, 502, 503, 506,
-  511, 512, 514, 517, 518, 521, 523, 524, 527, 529, 530, 533, 536, 544, 545,
-  547, 548, 551, 553, 556, 560, 562, 569, 571, 574, 575, 577, 581, 583, 584,
-  587, 589, 593, 599, 604, 605, 608, 610, 611, 614, 617, 620, 623, 625, 628,
-  631, 632, 634, 637, 638, 640, 641, 644, 647, 652, 653, 658, 659, 661, 667,
-  670, 671, 676, 683, 691, 692, 694, 697, 698, 704, 706, 707, 712, 713, 716,
-  719, 722, 724, 727, 731, 733, 734, 736, 737, 746, 749, 751, 757, 763, 766,
-  769, 770, 773, 775, 785, 788, 790, 791, 793, 794, 797, 799, 800, 802, 806,
-  808, 809, 814, 815, 820, 821, 823, 824, 826, 832, 844, 847, 848, 851, 853,
-  859, 862, 865, 868, 871, 874, 880, 881, 883, 890, 892, 895, 896, 901, 902,
-  905, 908, 920, 923, 926, 932, 934, 938, 941, 944, 953, 961, 962, 964, 967,
-  968, 977, 979, 982, 989, 991, 1000, 1001, 1003, 1004, 1012, 1015, 1019,
-  1021, 1024, 1028, 1031, 1034, 1037, 1042, 1046, 1057, 1061, 1067, 1072,
-  1079, 1088, 1090, 1093, 1094, 1103, 1106, 1112, 1121, 1124, 1127, 1133,
-  1138, 1142, 1145, 1148, 1154, 1157, 1166, 1168, 1169, 1178, 1183, 1205,
-  1208, 1216, 1219, 1220, 1223, 1225, 1234, 1240, 1243, 1246, 1247, 1250,
-  1262, 1265, 1267, 1271, 1280, 1288, 1289, 1294, 1295, 1303, 1304, 1307,
-  1315, 1339, 1342, 1366, 1382, 1393, 1396, 1412, 1415, 1417, 1423, 1424,
-  1432, 1448, 1466, 1468, 1474, 1487, 1498, 1501, 1502, 1514, 1523, 1525,
-  1538, 1543, 1546, 1549, 1561, 1565, 1570, 1577, 1580, 1582, 1607, 1612,
-  1642, 1649, 1664, 1667, 1691, 1717, 1735, 1762, 1780, 1783, 1784, 1840,
-  1846, 1852, 1859, 1864, 1868, 1876, 1879, 1888, 1897, 1927, 1928, 1934,
-  1949, 1954, 1964, 1982, 2009, 2024, 2030, 2038, 2042, 2053, 2057, 2062,
-  2065, 2092, 2114, 2147, 2173, 2188, 2203, 2224, 2233, 2237, 2239, 2266,
-  2276, 2293, 2333, 2345, 2383, 2432, 2438, 2441, 2446, 2450, 2468, 2501,
-  2530, 2560, 2576, 2659, 2732, 2735, 2786, 2813, 2848, 2915, 2948, 2957,
-  2981, 3031, 3046, 3076, 3115, 3157, 3160, 3164, 3185, 3193, 3298, 3407,
-  3560, 3619, 3737, 3752, 3856, 3898, 3971, 3985, 4076, 4228, 4478, 4853,
-  5896, 6115, 8561, 12230, 15899, 17122, 20791, 23237, 28129, 30575, 35467,
-  37913, 45251, 56258, 57481, 75826, 81941, 86833, 108847, 114962, 163882,
-  164617, 173666, 217694, 329234, 658468, 823085, 1152319, 1316936, 1646170,
-  1810787, 2798489, 3127723, 3292340, 3621574, 3786191, 4773893, 5761595,
-  6090829, 6255446, 6584680, 6749297, 7243148, 8066233, 9053935, 9547786,
-  12675509, 13498594, 21894061, MPD_SIZE_MAX
-};
-static const mpd_size_t c27[] = {
-  1, 2, 4, 5, 7, 10, 11, 13, 14, 17, 19, 20, 22, 23, 26, 31, 35, 37, 43, 47, 52,
-  55, 59, 61, 65, 67, 70, 71, 74, 83, 85, 89, 91, 94, 130, 131, 134, 142, 163,
-  182, 188, 268, 329, 335, 517, 611, 658, 670, 799, 893, 1034, 1081, 1222, 1273,
-  1457, 2021, 2444, 2867, 3149, 3337, 4277, 6298, 12596, 127867, 255734, 511468,
-  639335, 1278670, 1406537, 6009749, 8567089, 12019498, 24038996, 42835445,
-  MPD_SIZE_MAX
-};
-static const mpd_size_t c28[] = {
-  1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 34,
-  35, 37, 38, 40, 41, 43, 44, 46, 49, 50, 52, 53, 55, 56, 58, 61, 62, 65, 67,
-  68, 70, 71, 73, 74, 76, 77, 79, 82, 83, 85, 86, 88, 92, 95, 98, 100, 101, 103,
-  104, 106, 107, 109, 110, 113, 115, 116, 119, 121, 122, 124, 125, 127, 130,
-  131, 133, 134, 136, 137, 140, 142, 143, 145, 146, 151, 152, 154, 155, 158,
-  161, 164, 166, 167, 170, 172, 173, 175, 181, 185, 190, 191, 193, 196, 197,
-  200, 203, 205, 206, 209, 214, 217, 218, 221, 226, 230, 232, 238, 239, 242,
-  244, 247, 248, 253, 254, 259, 260, 265, 266, 269, 271, 274, 280, 281, 284,
-  289, 292, 293, 299, 301, 310, 311, 313, 316, 323, 325, 328, 334, 340, 341,
-  343, 344, 346, 347, 350, 355, 359, 362, 365, 367, 370, 371, 379, 380, 382,
-  385, 386, 392, 395, 397, 403, 406, 415, 427, 428, 431, 442, 449, 452, 457,
-  461, 463, 473, 476, 478, 484, 488, 491, 494, 506, 509, 518, 521, 529, 530,
-  532, 538, 539, 545, 548, 551, 563, 578, 586, 587, 593, 595, 598, 601, 613,
-  622, 626, 629, 632, 643, 646, 659, 665, 667, 671, 685, 686, 710, 721, 730,
-  731, 737, 758, 760, 770, 790, 835, 851, 854, 862, 883, 887, 905, 914, 923,
-  926, 937, 952, 956, 983, 1009, 1012, 1025, 1069, 1126, 1156, 1172, 1241,
-  1244, 1258, 1273, 1372, 1420, 1447, 1495, 1507, 1580, 1670, 2111, 2138,
-  15683, 31366, 51349, 62732, 78415, 102698, 109781, 125464, 156830, 172513,
-  203879, 219562, 266611, 313660, 345026, 360709, 392075, 407758, 439124,
-  454807, 486173, 533222, 548905, 580271, 627320, 643003, 674369, 690052,
-  721418, 768467, 784150, 815516, 831199, 862565, 878248, 909614, 972346,
-  1019395, 1050761, 1066444, 1113493, 1144859, 1160542, 1207591, 1301689,
-  1348738, 1380104, 1442836, 1536934, 1568300, 1583983, 1615349, 1631032,
-  1662398, 1725130, 1772179, 1803545, 1819228, 1897643, 1944692, 1960375,
-  1991741, 2038790, 2054473, 2101522, 2226986, 2242669, 2274035, 2289718,
-  2368133, 2415182, 2430865, 2524963, 2603378, 2619061, 2697476, 2713159,
-  2744525, 2838623, 2901355, 2995453, 3026819, 3073868, 3089551, 3136600,
-  3183649, 3215015, 3403211, 3465943, 3544358, 3607090, 3638456, 3795286,
-  3967799, 3983482, 4061897, 4077580, 4155995, 4218727, 4406923, 4453972,
-  4532387, 4720583, 4877413, 5238122, 5347903, 5394952, 5442001, 5677246,
-  5724295, 5802710, 5818393, 5990906, 6037955, 6053638, 6147736, 6367298,
-  6508445, 6759373, 6931886, 7041667, 7088716, 7167131, 7590572, 8123794,
-  8829529, 9064774, 9425483, 9754826, 10335097, 11307443, 11448590, 13518746,
-  18129548, MPD_SIZE_MAX
-};
-static const mpd_size_t c29[] = {
-  1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59,
-  61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113,
-  115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157,
-  161, 167, 169, 173, 175, 179, 181, 185, 187, 191, 197, 203, 209, 211, 215,
-  217, 223, 227, 233, 235, 239, 241, 245, 247, 251, 253, 257, 259, 263, 265,
-  269, 271, 275, 277, 281, 283, 289, 293, 295, 299, 305, 307, 313, 317, 319,
-  323, 329, 337, 341, 343, 347, 349, 353, 355, 359, 367, 371, 373, 377, 379,
-  383, 385, 389, 395, 397, 407, 413, 415, 419, 425, 427, 431, 433, 437, 443,
-  445, 449, 455, 457, 469, 479, 481, 485, 487, 491, 493, 497, 499, 503, 511,
-  517, 523, 529, 533, 535, 539, 541, 547, 553, 557, 565, 569, 575, 589, 593,
-  599, 605, 611, 617, 619, 623, 635, 637, 641, 643, 649, 653, 655, 661, 677,
-  679, 685, 701, 703, 707, 715, 719, 721, 727, 731, 739, 743, 745, 755, 761,
-  769, 775, 781, 785, 787, 793, 797, 799, 821, 823, 829, 845, 853, 863, 871,
-  881, 895, 907, 917, 919, 929, 935, 941, 943, 947, 949, 955, 961, 967, 973,
-  977, 979, 991, 997, 1001, 1003, 1007, 1015, 1019, 1027, 1031, 1033, 1043,
-  1045, 1049, 1051, 1057, 1063, 1067, 1073, 1075, 1079, 1085, 1087, 1093,
-  1097, 1099, 1109, 1117, 1129, 1147, 1151, 1157, 1165, 1169, 1171, 1187,
-  1189, 1199, 1201, 1205, 1207, 1211, 1213, 1219, 1235, 1237, 1247, 1249,
-  1259, 1261, 1265, 1271, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
-  1313, 1315, 1319, 1321, 1327, 1343, 1345, 1367, 1369, 1375, 1385, 1387,
-  1399, 1403, 1409, 1423, 1427, 1439, 1441, 1453, 1463, 1477, 1487, 1499,
-  1501, 1511, 1523, 1525, 1535, 1565, 1595, 1627, 1631, 1633, 1637, 1649,
-  1657, 1673, 1685, 1687, 1699, 1705, 1711, 1715, 1727, 1745, 1751, 1757,
-  1771, 1811, 1823, 1829, 1843, 1865, 1873, 1897, 1957, 1963, 1967, 1975,
-  1979, 2017, 2039, 2065, 2075, 2093, 2143, 2153, 2191, 2207, 2231, 2339,
-  2359, 2405, 2425, 2437, 2443, 2471, 2473, 2479, 2507, 2533, 2573, 2579,
-  2581, 2617, 2645, 2651, 2695, 2729, 2813, 2827, 2867, 2941, 2959, 3007,
-  3031, 3055, 3059, 3085, 3173, 3181, 3197, 3221, 3247, 3275, 3377, 3395,
-  3467, 3505, 3521, 3553, 3559, 3589, 3607, 3611, 3671, 3715, 3875, 3977,
-  3983, 4049, 4129, 4171, 4183, 4187, 4315, 4559, 4691, 4753, 4777, 4807,
-  4993, 5141, 5155, 5167, 5279, 5495, 5509, 5723, 5735, 5917, 6017, 6499,
-  6887, 7081, 7217, 7265, 7663, 8051, 8245, 9215, 9797, 9991, 10379, 10573,
-  11155, 11341, 11737, 12319, 13403, 13483, 13871, 14065, 14453, 15035, 15617,
-  16105, 17527, 17557, 18139, 18527, 19589, 22547, 22795, 23183, 23713, 25775,
-  29585, 29899, 30361, 31331, 31961, 35431, 36085, 38147, 41873, 42271, 44333,
-  48457, 50519, 54643, 54757, 55193, 56705, 60829, 62891, 67015, 69077, 73201,
-  74083, 75263, 75757, 79387, 80525, 81449, 85573, 87635, 91759, 93409, 93821,
-  97945, 99851, 100007, 104131, 106193, 110317, 112735, 116503, 118565, 119177,
-  122689, 124751, 128875, 130937, 135061, 137123, 141247, 147433, 149495,
-  151387, 153619, 159805, 161867, 165991, 170713, 172177, 174239, 178363,
-  180425, 184549, 186611, 190735, 192797, 196481, 196921, 215479, 217541,
-  221665, 223727, 228691, 229913, 234037, 240223, 242285, 248471, 252595,
-  254459, 254657, 258781, 260843, 264967, 267029, 271153, 273215, 277339,
-  279401, 285587, 291773, 297959, 304145, 308269, 312437, 316517, 322703,
-  326827, 328889, 333013, 339199, 347447, 351571, 353633, 357757, 359819,
-  363943, 366005, 378377, 382501, 384563, 388687, 390749, 394873, 396935,
-  401059, 407245, 419617, 425803, 427865, 431989, 438175, 440237, 441277,
-  446423, 450547, 469105, 471167, 483539, 486371, 493849, 495911, 499255,
-  500035, 502097, 506221, 508283, 533027, 539213, 545399, 549523, 551585,
-  555709, 557771, 582515, 586639, 592825, 607259, 611383, 629941, 636127,
-  642313, 673243, 681491, 697987, 700049, 706235, 722731, 724793, 741289,
-  743351, 766033, 784591, 799025, 809335, 817583, 821707, 871195, 889753,
-  922745, 935117, 945427, 947489, 963985, 970171, 972233, 984605, 990791,
-  1007287, 1021721, 1027907, 1032031, 1034093, 1038217, 1050589, 1075333,
-  1100077, 1106263, 1112449, 1120697, 1126883, 1163999, 1242355, 1244417,
-  1275347, 1285657, 1298029, 1300091, 1310401, 1328959, 1331021, 1368137,
-  1384633, 1386695, 1411439, 1427935, 1442369, 1562185, 1681561, 1683623,
-  1687747, 1700119, 1751669, 1757855, 1825901, 1900133, 2036225, 2079527,
-  2187059, 2500175, 2652763, 2778545, 2914637, 3320851, 3500245, 3663143,
-  3700259, 4100287, 4300301, 4700329, 4900343, 5300371, 5900413, 6100427,
-  7100497, 7900553, 8300581, 8500595, 10300721, 10700749, 10935295, 14301001,
-  16604255, 23245957, 23501645, 36529361, 43171063, 56454467, 83021275,
-  96304679, 156079997, 176005103, 322122547, MPD_SIZE_MAX
-};
-static const mpd_size_t c30[] = {
-  1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31,
-  32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 50, 52, 53, 55, 56, 58, 61, 62,
-  64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91,
-  92, 94, 95, 97, 100, 101, 103, 104, 106, 107, 109, 110, 112, 113, 115, 116,
-  119, 122, 124, 125, 127, 128, 130, 133, 134, 136, 137, 142, 143, 145, 146,
-  148, 149, 152, 154, 155, 157, 158, 160, 161, 163, 164, 166, 167, 172, 175,
-  176, 178, 179, 181, 182, 185, 187, 190, 193, 194, 197, 199, 200, 202, 203,
-  205, 206, 208, 209, 211, 212, 214, 215, 217, 218, 220, 221, 223, 224, 226,
-  227, 229, 230, 232, 235, 238, 239, 244, 250, 251, 253, 254, 256, 257, 259,
-  260, 263, 265, 266, 268, 269, 271, 272, 275, 277, 284, 286, 287, 290, 292,
-  296, 298, 299, 304, 308, 311, 313, 316, 317, 319, 320, 322, 323, 325, 326,
-  328, 329, 331, 332, 334, 335, 337, 344, 347, 349, 353, 355, 356, 358, 359,
-  362, 364, 365, 367, 370, 371, 373, 374, 377, 379, 380, 383, 385, 386, 388,
-  389, 391, 394, 395, 397, 398, 401, 403, 404, 407, 410, 415, 416, 421, 422,
-  424, 425, 430, 431, 433, 434, 436, 437, 440, 442, 443, 446, 448, 449, 451,
-  452, 457, 458, 463, 464, 467, 470, 475, 488, 491, 499, 500, 503, 505, 506,
-  508, 511, 512, 514, 515, 518, 520, 521, 523, 526, 527, 530, 532, 533, 535,
-  538, 541, 542, 544, 547, 550, 553, 554, 557, 559, 565, 568, 569, 571, 572,
-  574, 575, 577, 580, 584, 587, 589, 592, 593, 595, 598, 599, 601, 611, 616,
-  619, 622, 623, 625, 626, 629, 631, 632, 635, 638, 640, 641, 646, 650, 652,
-  656, 658, 659, 661, 662, 664, 667, 668, 670, 673, 677, 679, 689, 691, 694,
-  697, 698, 706, 707, 709, 712, 713, 716, 718, 725, 728, 734, 737, 739, 742,
-  748, 757, 758, 760, 761, 769, 770, 772, 773, 776, 778, 779, 781, 782, 788,
-  790, 791, 793, 794, 796, 799, 802, 806, 809, 814, 817, 821, 827, 829, 830,
-  832, 835, 844, 862, 868, 872, 874, 880, 884, 887, 892, 893, 896, 901, 902,
-  911, 919, 925, 928, 935, 943, 965, 971, 977, 982, 983, 985, 991, 1000,
-  1010, 1012, 1015, 1016, 1019, 1022, 1024, 1025, 1027, 1028, 1030, 1031,
-  1033, 1036, 1043, 1049, 1054, 1060, 1061, 1064, 1066, 1070, 1073, 1082,
-  1084, 1100, 1106, 1114, 1130, 1133, 1136, 1148, 1154, 1160, 1168, 1169,
-  1174, 1178, 1181, 1184, 1201, 1232, 1237, 1241, 1249, 1250, 1252, 1258,
-  1261, 1262, 1264, 1270, 1271, 1285, 1291, 1292, 1301, 1304, 1307, 1318,
-  1322, 1324, 1334, 1336, 1343, 1354, 1369, 1373, 1379, 1381, 1382, 1385,
-  1388, 1391, 1393, 1396, 1414, 1427, 1429, 1432, 1436, 1439, 1456, 1468,
-  1477, 1489, 1495, 1496, 1516, 1520, 1522, 1531, 1538, 1544, 1552, 1555,
-  1576, 1582, 1588, 1589, 1592, 1595, 1598, 1612, 1615, 1618, 1625, 1627,
-  1634, 1639, 1642, 1649, 1651, 1654, 1675, 1693, 1709, 1724, 1759, 1765,
-  1774, 1781, 1783, 1792, 1802, 1822, 1838, 1847, 1856, 1873, 1921, 1925,
-  1945, 1951, 2005, 2021, 2029, 2044, 2048, 2050, 2077, 2105, 2108, 2120,
-  2123, 2146, 2155, 2164, 2177, 2191, 2200, 2212, 2215, 2260, 2266, 2272,
-  2293, 2308, 2315, 2320, 2341, 2356, 2413, 2455, 2495, 2498, 2522, 2540,
-  2584, 2602, 2629, 2635, 2648, 2672, 2723, 2738, 2759, 2765, 2782, 2786,
-  2833, 2878, 2917, 2954, 2978, 3017, 3110, 3145, 3236, 3350, 3383, 3391,
-  3427, 3448, 3529, 3593, 3676, 4310, 4351, 4640, 4741, 4993, 5603, 5789,
-  6034, 6896, 6973, 7327, 8189, 8620, 9482, 10775, 12068, 12499, 13361,
-  13792, 14654, 15085, 17240, 18533, 21550, 22843, 24136, 24998, 26291,
-  26722, 28015, 28877, 29308, 30601, 31463, 36635, 38359, 39221, 41807,
-  43100, 45686, 46979, 48703, 49996, 51289, 52582, 57754, 58616, 59047,
-  61633, 62926, 70253, 76718, 96113, 97406, 98699, 102578, 113353, 142661,
-  153005, 7473841, 37369205, 52316887, 82212251, 97159933, 142002979,
-  171898343, 231689071, 261584435, 351270527, MPD_SIZE_MAX
-};
-
-#ifdef CONFIG_64
-
-#if MPD_SIZE_MAX != 18446744073709551615ULL
-  #error "transpose3: need 64 bits for MPD_SIZE_MAX"
-#endif
-/* Maximum n for 3 * 2^n matrix, limited by log2(2^n/BMEMB) <= 30.
- * This limit can be raised by increasing BMEMB or by extending
- * the above cycle tables beyond 30. */
-#define MAXN  42
-#define BMEMB 4096     /* block members */
-
-/* END CONFIG_64 */
-#else
-
-#if MPD_SIZE_MAX != 4294967295UL
-  #error "transpose3: need 32 bits for MPD_SIZE_MAX"
-#endif
-#define MAXN 30        /* maximum n for 3 * 2^n matrix, limited by MPD_SIZE_MAX */
-#define BMEMB 4096     /* block members */
-
-#endif /* END CONFIG_32 */
-
-
-/* all cycles */
-static const mpd_size_t *start[] = {
-  c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16,
-  c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29, c30
-};
-
-
-
-/*
- * Block transpose on a 3 x 2^n or a 2^n x 3 matrix. 2^n is split into
- * nprime blocks of size BMEMB, and the blocks are transposed cyclically.
- */
-static void
-_block_transpose_3xpow2(mpd_uint_t *matrix, mpd_size_t rows, mpd_size_t cols)
-{
-	mpd_uint_t buf1[BMEMB];
-	mpd_uint_t buf2[BMEMB];
-	mpd_uint_t *readbuf, *writebuf;
-	mpd_size_t nprime;  /* number of blocks per row (or column) */
-	mpd_size_t log2n;
-	mpd_size_t a, mod;
-	mpd_size_t s, next;
-	mpd_size_t i;
-
-
-	if (rows == 3) {
-		nprime = cols / BMEMB;
-		a = 3;
-	}
-	else { /* cols == 3 */
-		nprime = rows / BMEMB;
-		a = nprime;
-	}
-
-	log2n = BSR(nprime);
-	mod = 3 * nprime - 1;
-
-	for (i = 0; start[log2n][i] != MPD_SIZE_MAX; i++) {
-
-		s = start[log2n][i];
-
-		readbuf = buf1; writebuf = buf2;
-
-		memcpy(readbuf, matrix+BMEMB*s, BMEMB*(sizeof *readbuf));
-
-		pointerswap(&readbuf, &writebuf);
-		next = mulmod_size_t(s, a, mod);
-
-		while (next != s) {
-
-			memcpy(readbuf, matrix+BMEMB*next, BMEMB*(sizeof *readbuf));
-			memcpy(matrix+BMEMB*next, writebuf, BMEMB*(sizeof *writebuf));
-
-			pointerswap(&readbuf, &writebuf);
-			next = mulmod_size_t(next, a, mod);
-
-		}
-
-		memcpy(matrix+BMEMB*next, writebuf, BMEMB*(sizeof *writebuf));
-	}
-}
-
-
-/*
- * In place transposition of 3 x 2^n or 2^n x 3 matrix.
- * Maximum size: 3 x 2^MAXN or 2^MAXN x 3
- */
-void
-transpose_3xpow2(mpd_uint_t *matrix, mpd_size_t rows, mpd_size_t cols)
-{
-	mpd_uint_t buf[3*BMEMB];
-	mpd_uint_t *p;
-	mpd_size_t msize, bsize;
-
-	msize = mul_size_t(rows, cols);
-	bsize = 3*BMEMB;
-
-	if (msize <= bsize) {
-		std_trans(buf, matrix, rows, cols);
-		memcpy(matrix, buf, msize * (sizeof *matrix));
-	}
-	else if (rows == 3) {
-		assert(ispower2(cols));
-		assert(BSR(cols) <= MAXN);
-
-		_block_transpose_3xpow2(matrix, rows, cols);
-		for (p = matrix; p < matrix+msize; p += bsize) {
-			std_trans(buf, p, rows, BMEMB);
-			memcpy(p, buf, bsize * (sizeof *matrix));
-		}
-	}
-	else if (cols == 3) {
-		assert(ispower2(rows));
-		assert(BSR(rows) <= MAXN);
-
-		for (p = matrix; p < matrix+msize; p += bsize) {
-			std_trans(buf, p, BMEMB, cols);
-			memcpy(p, buf, bsize * (sizeof *matrix));
-		}
-		_block_transpose_3xpow2(matrix, rows, cols);
-	}
-	else {
-		mpd_err_fatal("transpose_3xpow2: wrong input for rows or cols");
-	}
-}
-
-


More information about the Python-checkins mailing list