Karatsuba-Ofman multiplication algorithm.

[u/mdw/catacomb] / tests / mpx

diff --git a/tests/mpx b/tests/mpx
index 45f7705..a9490cd 100644 (file)
--- a/tests/mpx
+++ b/tests/mpx
@@ -1,6 +1,6 @@
 # Test vectors for low-level MP functions
 #
-# $Id: mpx,v 1.2 1999/11/14 13:53:12 mdw Exp $
+# $Id: mpx,v 1.3 1999/12/10 23:26:40 mdw Exp $
 
 # --- Load-store tests ---
 #
@@ -490,6 +490,50 @@ umul {
   08d95fc1d6dd6b9423c7bb033598df0c
   6c03f5958677efd383509141bf257375
   03bbd76f19ba19e3f255c24063f6384d4ac913d9e582392589a525195bcc547c;
+
+  # --- Karatsuba regression ---
+  #
+  # This bug was caused by kmul (a) choosing the split point too low on 
+  # odd-sized inputs and (b) not allocating enough workspace.
+
+  21a9269d7b8b63cf18faa933b3c868ba1e8cb3f00b57e197709abf96eeb9bf12e8fe22b3
+  0144c992b68e3ca712678215d5bc968702ccfea17717737ba501a38d26fa5091ba
+  2ab495f91afd7c36f85ece6fd58577f995de88d62a98a07c6d9e3500ae67b0f100bc709d1f30894662774d0cadfba091788c427cc6f4bacb26e42cf92f6e4494e03c990e;
+
+  # --- Larger number tests for Karatsuba ---
+
+  416e63549e2cf08fb225058b3545cb4a47cbf9
+  de38c473c27f7bdef02a084192b3e17f435cf7
+  38cc3c7f360737411df7b52a222a3672c6e0d39f0a868479176a6143e1129d44d5aa61be493f;
+
+  aa20b1355073f21c57530d2f90bc40e47ac463
+  8315dfa60e97ff3dab7a6f61fcec2cd5b6f127
+  571d43fda6ce14a78534ac72c50b58738d62630766a59a7cec1a63433e499b1b5eac5ef71e15;
+
+  f641594177c8c364d922c659a8f7ae0460c7d74b266c8cc258ad5f
+  5948dd29fc5172c37c31da6957779a1bebe452d8deba26c5d3d390
+  55e2cf27aa49f938584dca4044d944077e226206c6f8c7688e8760f3b5c106413fd0ef4b63a97991da86fd113ff4822a41f76913d270;
+
+  a4170f55dfa135c4bdd3a921a8c1567eebc6b799fb62b0dd27b089
+  7b7d619e07a5d01427348c05605f67196b2923b074787c375977ac
+  4f277232c75290f0c5fed384dba2aaa23fe4a360ea63ee45fb6c0134b36a09a9163f3c767d498b8dcd31e5deaef386d4a9b7d85b4b0c;
+
+  250e7a0c7035df81429572d3f772720e723b710d54b9eb5f16814117980f0559bf12b82e00c5b3904e
+  1be3c88b01ce53a70c12f74dcc247823846ac6c06a9cb41b86794900006045f05e29da23b81523aa9f
+  04097fbcf75616fef7b6b91680963f7e0cf1bf72bc5f453e46136fc92b20ae8a30d7ae7965f8271de854442b93562ebaa9ee09fba4a7b79ef8b26718b12424419dc301496dc0d6cfb04e4f7a3a3729046c72;
+
+  af3148a72dcf1340f6b5a3b2fc1cacd7e6f9e60a13de5c91c37bb850f0e930683c2dc96882a9f62b76
+  48603cc656908b34c70ed826da8c3414d5845100f53cb6f9f370a4c7708a9b8ffd787537048f89493a
+  3187b8818bf644805c880d189bbf606ca23e01431cf5b3b633db48a1202aa346f6a0e3958c7264fa1de2d92660345e820f4f3659cf0040a28fb9b725f7ab83610c9c056062326f776ce871696eede0507ebc;
+
+  0b1cc934a2f6244b93c8ac10881de20349d133642ac19fa0be3acacbf4429d0ec7bbad2f41534a693647b7c02e683cde249e36f008fb68e96de65c8a268eb1ea
+  12444899c13f0ee85a4f47024f06d8a5746f0d9fec02e57c6d87a7bba17c1454fe6387bff5b96e38ce6142b9eebe249865c52b617b8966e6f93b16f612a91155
+  cafcf1ea9f16a56f9ac4635d58992a789c51b6d7e53b5e1d8b59d5c1850c5c6ac2297839af44b29d5cf440772f98fd9d090ccec2d56adeb113bd3459d620b0b02679b72f3170ea8e2bd4486eebf2496d8be01cfe86923e5bbeb6f91582dfb95c6ef0a52cbc068081dc363b31dbd2ed80e3267d973ea39f82e276002eab9cb2;
+
+  3ba5a9c550b8cf6c3b87cc106b6551221a0dc90ac193ebcc526e4e5f53cf012fa6e05b155dcb3c4c0e1a90a01062a67ec434f6744195349194770711ea836a8b
+  54f04f121d22db842523e9bf75727d5b0e9ef17e6d727918894927fade87ceeb2106684c4af7c49653425e29f7a91abf8adec4de2ca499df2534644397e454ac
+  13ca59703f4c087c16a9a7bc7022904a37a469c1d0fd9fa7ffabe8f7d887fe1572c0bf5c75fde6913b565f8106bba9c26c9bbce190a9b8967112d74c0ac3d4ff9d2a385b96833e3c456d5601c74d8d2c9fff35abc60e7cc15d7c680f20757c13a415f1b8fbe3c6c32434aa36c528473dd20ea39f0e5ee22d1cd23040900d3164;
+
 }
 
 usqr {