 My Math Forum Binary Multiplication of two 1024bit numbers
 User Name Remember Me? Password

 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 Search tags for this page

,

,

### 1024 bit multiplication

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.       