My Math Forum Binary Multiplication of two 1024bit numbers

 Applied Math Applied Math Forum

 April 25th, 2013, 06:52 AM #1 Newbie   Joined: Apr 2013 Posts: 1 Thanks: 0 Binary Multiplication of two 1024bit numbers Hi everyone, Is there a efficient way to multiply of two 1024-bit binary numbers using fixed sized (for example 32-bits) blocks? For simplicity lets take an example of two 8-bit numbers. A2 A1 A = 1001 1101 B2 B1 B = 1100 1110 So instead of multiplying AxB I want to do: Step 1: A1xB1 and store the value (=X) Step 2: A2xB2 and store the value (=Y) Step 3: Find some relation between X and Y I cannot think of step 3. So can someone help me with this please. Is it even possible to realize multiplication that way? Regards, Jack
April 25th, 2013, 09:08 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Binary Multiplication of two 1024bit numbers

Quote:
 Originally Posted by prakha Hi everyone, Is there a efficient way to multiply of two 1024-bit binary numbers using fixed sized (for example 32-bits) blocks? For simplicity lets take an example of two 8-bit numbers. A2 A1 A = 1001 1101 B2 B1 B = 1100 1110 So instead of multiplying AxB I want to do: Step 1: A1xB1 and store the value (=X) Step 2: A2xB2 and store the value (=Y) Step 3: Find some relation between X and Y I cannot think of step 3. So can someone help me with this please. Is it even possible to realize multiplication that way?

You need A2*A2*16^2 + (A1*B2+A2*B1)*16 + A1*B1. This can be extended to larger numbers in a straightforward way. Keeping track of carries is the hardest part; it's often convenient to use assembly language for this purpose.

At 1024 bits you'll probably realize a slight speedup with Karatsuba rather than schoolbook multiplication.

 Tags 1024bit, binary, multiplication, numbers

,

,

1024 bit multiplication

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post mhhojati Number Theory 3 November 5th, 2013 10:04 PM Jet1045 Number Theory 3 February 12th, 2013 05:47 AM Tylerman Applied Math 3 February 13th, 2012 12:14 AM johnny Computer Science 6 October 18th, 2007 10:29 AM johnny Computer Science 2 October 13th, 2007 02:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top