Need some clarity on pseudo code function

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 988 Views - Last Post: 22 September 2015 - 06:33 PM Rate Topic: -----

#1 Eshua  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 38
  • Joined: 11-May 14

Need some clarity on pseudo code function

Posted 22 September 2015 - 10:22 AM

I'm trying to figure out how to implement the multiplication pseudo code for Binary Numbers (any size binary number, could possibly be a binary number with 12000 0's or 1's.) that is given to us in the lecture notes:

Attached Image


and I don't understand what z is supposed to be? For example here is what I have:


Attached Image

I'm trying to clearly understand what z is being used for. (NOTE: I 'm assuming z is some product vector I could possibly return that's why my return type is a
vector
of integers, but again, I am not quite surebecause this pseudo code is extremely vague.

Is This A Good Question/Topic? 0
  • +

Replies To: Need some clarity on pseudo code function

#2 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3778
  • View blog
  • Posts: 13,688
  • Joined: 08-August 08

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 10:59 AM

There is no vector. The variables x,y, and z are integers. The size(y) indicates the number of bits used, so 0100 would be 3, since the zeroes to the left of the 1 don't matter.
Was This Post Helpful? 0
  • +
  • -

#3 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 457
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 01:17 PM

I disagree, there's no std::vector per se, though you can implement this vector of 0s and 1s using, say, std::vector<bool> and an addition function.

In that case x and y are vectors of 0s and 1s, as is z which is the resulting vector of 0s and 1s after multiplication.

z = z + x is binary addition of two vectors of 0s and 1s. : P

This post has been edited by Xupicor: 22 September 2015 - 01:17 PM

Was This Post Helpful? 1
  • +
  • -

#4 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3778
  • View blog
  • Posts: 13,688
  • Joined: 08-August 08

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 01:24 PM

Yes, but you don't need the vector. As a comparison, I could make a vector of char to form a string, but why?


By the way, that algorithm doesn't look right to me. Doing it by hand, for multiply(5,4) I calculate 5.

Ok, I must have done something wrong by hand. Doing it in code produces expected values.

This post has been edited by CTphpnwb: 22 September 2015 - 01:36 PM

Was This Post Helpful? 0
  • +
  • -

#5 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 457
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 02:00 PM

std::vector<bool> should be (implementation defined if and how) optimized to hold bool values in a way that one bool would use one bit of memory, instead of sizeof(bool) bytes of memory. Though if you want to specifically avoid this specialization - there's always std::vector<char>.

So, I don't quite see your point. What does a string has to do with it? (Sometimes you need std::string, sometimes you need std::vector<char>, usually for quite different purposes, again, don't see your point)


Also, the algorithm looks fine to me. The thing is - y[0] is the least significant bit. I went through it on paper and it seems to work fine for 4*2, 12*3, 5*4, 26*14...

This post has been edited by Xupicor: 22 September 2015 - 02:01 PM

Was This Post Helpful? 0
  • +
  • -

#6 CTphpnwb  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 3778
  • View blog
  • Posts: 13,688
  • Joined: 08-August 08

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 02:04 PM

My point is that with a little bit shifting you don't need a vector. All you need are three bytes: x, y, and z. Oh, and a for loop, so I guess you might count i too.
Was This Post Helpful? 0
  • +
  • -

#7 Eshua  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 38
  • Joined: 11-May 14

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 03:05 PM

I do in fact need the vector. My question is: should my z be a vector that initially has one element, 0?

Also, why am i multiplying 2 by my empty element vector z that currently contains nothing? What is that accomplishing? What is multiplying by 2 accomplishing regardless?
Was This Post Helpful? 0
  • +
  • -

#8 Eshua  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 38
  • Joined: 11-May 14

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 03:47 PM

I can't seem to grasp what you are saying Xupicor. I mean it sounds correct but I am either implementing the pseudocode wrong or I am not computing correctly. Here is my implementation of the pseudo code. Assume that my numbers are 1011 ( vector x) ][1,0,1,1] and lets say im multiplying that by vector y 0011 (11 * 3)
:
vector<int> multiplyBinaryNumbers(vector<int> x, vector<int> y)
{
	//Product Vector?
	vector<int> z = {0,0,0,0};

	for (int i = y.size() - 1; i >= 0; i--)
	{
		// Assume We have 1011 * 0011. Where x is 1011 and y is 0011
		
		//Uhh?Am I doing this right
		z.push_back(2 * z[i]);

		//If y is odd
		if (y[i] % 2 != 0)
		{
			//Is this what they want?
			z.push_back(z[i] + x[i]);
		}
	}
	//Return product
	return z;
}


I got:

i = 3
i = 2
i = 1
i = 0
z vector:
0 0 0 0 0 1 0 1 0 0
which = 20 not 33 :(/>/>/>/> Am I missing something obvious here? Again, thank you all for your help

This post has been edited by Eshua: 22 September 2015 - 03:53 PM

Was This Post Helpful? 0
  • +
  • -

#9 Eshua  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 38
  • Joined: 11-May 14

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 03:52 PM

Note: I should be getting 100001 which is 33. I know i have to be implementing this incorrectly.
Was This Post Helpful? 0
  • +
  • -

#10 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 457
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 05:02 PM

View PostCTphpnwb, on 23 September 2015 - 12:04 AM, said:

My point is that with a little bit shifting you don't need a vector. All you need are three bytes: x, y, and z. Oh, and a for loop, so I guess you might count i too.
Three bytes? What about the part where x/y can be 12000 bits long? Unless you know of an implementation with 12000 bits wide bytes... ; )


@Eshua - go through the algorithm on paper a couple of times. In pseudocode you can substitute the z = z * 2 multiplication with z = z + z.
You're supposed to add a binary number z to itself. It effectively shifts bits by one position.
So no, your line 11 is completely wrong.

Why do you use a vector of ints? Is one int supposed to be representing one bit in your code? Then why not use vector<bool> where bool will actually take up one bit of memory instead of 4/8 bytes (or whatever your implementation has it)?

Also, for this to work you need to develop an addition function that will take two vectors of bits (whatever you choose them to be in your implementation), treat them as binary numbers and commence with binary addition. Then you will be able to use this addition in line 11 and 17.
Again, you're supposed to treat these vectors as binary numbers and add them whole, not just particular elements (which you should treat as bits).

See this for inspiration: http://stackoverflow.../2412722/503757


edit: Maybe another take on it will clear up your confusion - do you know about classes? If so. you can make a class Binary that internally holds its bits in, say, a std::vector<bool> and exposes them through overloaded operator[]. Additionally, overload operator+ to be able to add two Binary objects. Once done you'll pretty much have what you need to complete your assignment by translating that above pseudocode to C++ as is (with the change of z = z * 2 to z = z + z). It can be implemented as overloaded binary operator*.

If you do this - x, y and z will be objects of type Binary. Does that make more sense?

This post has been edited by Xupicor: 22 September 2015 - 05:20 PM

Was This Post Helpful? 1
  • +
  • -

#11 Eshua  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 38
  • Joined: 11-May 14

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 05:13 PM

oh so in line 11 and line 17 I need to call my AddBinaryNumberFunction and pass those in as parms correct? then return the result into my z. vector

so like

z.push_back(ADDBINARYNUMBERS(z[i] + x[i]));


This post has been edited by Eshua: 22 September 2015 - 05:14 PM

Was This Post Helpful? 0
  • +
  • -

#12 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 457
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 05:23 PM

No, no, rather you'd need:
std::vector<bool> binary_add(const std::vector<bool>& x, const std::vector<bool>& y);

and use it in line 11 and 17:
z = binary_add(z, z); // z = z * 2
//...
z = binary_add(z, x); // z = z + x


See, the multiplication is fairly simple - it's the addition function that will actually crunch the bits individually. ; )

This post has been edited by Xupicor: 22 September 2015 - 05:25 PM

Was This Post Helpful? 0
  • +
  • -

#13 Eshua  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 38
  • Joined: 11-May 14

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 05:44 PM

Yeah , I don;t get it. I've traced through this vector over 50 times now. What are you getting when you go through? I even pretended, and did the binary addition and still didn't get anything correct

Am I correct in setting my vector z to have as many zeros as the size of my binary numbers have? Or should I set that vector to just 0.

This post has been edited by Eshua: 22 September 2015 - 05:44 PM

Was This Post Helpful? 0
  • +
  • -

#14 Eshua  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 38
  • Joined: 11-May 14

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 05:54 PM

UPDATE: Gonna trace through again lol
Was This Post Helpful? 0
  • +
  • -

#15 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 457
  • View blog
  • Posts: 1,179
  • Joined: 31-May 11

Re: Need some clarity on pseudo code function

Posted 22 September 2015 - 06:03 PM

You're talking about addition function, right? Well, depends on how you go about it - but yes, I would make the result vector size of the longer of the two operands, + 1 to accommodate possible carry over (11 + 11 is 110), then maybe trim that last element if it's 0. ; )
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2