My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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
prakha is offline  
 
April 25th, 2013, 09:08 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
1024bit, binary, multiplication, numbers



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
binary numbers mhhojati Number Theory 3 November 5th, 2013 10:04 PM
Coding Theory & Binary Numbers Jet1045 Number Theory 3 February 12th, 2013 05:47 AM
binary numbers between two points of a 9 number line Tylerman Applied Math 3 February 13th, 2012 12:14 AM
Binary Numbers johnny Computer Science 6 October 18th, 2007 10:29 AM
I need some help on binary, hexadecimal and decimal numbers! johnny Computer Science 2 October 13th, 2007 02:00 PM





Copyright © 2019 My Math Forum. All rights reserved.