Roast me

[highwayman]

Ok maybe not exactly, but I need someone to tell me the failings of my division function because it doesn’t feel right anyone mind helping me?

Sorry for not putting the code in directly it just too big and I couldn’t copy paste: https://repl.it/@Highwayman/BN

[whitenite1]

@highwayman

When I load your code into my MS Visual Studio, I get the following error
Error 1 error C4519: default template arguments are only allowed on a class. I get the same error 5 times, once for each template in your coding.

Your code is only 3000 bytes, so is NOT too large to be pasted here. Here it is.

#include <iostream>
#include <bitset>
using namespace std;


template <int size>
void inc(bitset<size>& a){
   for(int n = 0;n < size;n++){
      if(a[n] == 0){
         a.flip(n);
         break;
      }
      else{
         a.flip(n);
      }
   }
}

template <int bigger,int smaller,int newSize = bigger + 1>
bitset<newSize> add(bitset<bigger> a,bitset<smaller> b){
   bitset<newSize> result = 0;
   for(bitset<bigger> track = 0;track != a;inc<bigger>(track)){
      inc<newSize>(result);
   }
   for(bitset<smaller> track = 0;track != b;inc<smaller>(track)){
      inc<newSize>(result);
   }
   return result;
}

template <int bigger,int smaller,int newSize = bigger + smaller>
bitset<newSize> multiply(bitset<bigger> a,bitset<smaller> b){
   bitset<newSize> result = 0;
   for(bitset<smaller> track = 0;track != b;inc<smaller>(track)){
      result = add<newSize,bigger,newSize> (result,a);
   }
   return result;
}

template <int bSize,int eSize,int newSize = (bSize*eSize) + 1>
bitset<newSize> power(bitset<bSize> base,bitset<eSize> exponent){
	bitset<newSize> result = 0;
	result = add<newSize,bSize,newSize> (result,base);
	for(bitset<eSize> track = 1;track != exponent;inc<eSize>(track)){
		result = multiply<newSize,bSize,newSize> (result,base);
	}
	return result;
}

template <int size> 
void dec(bitset<size>& a){
	for(int n = 0;n < size;n++){
		a.flip(n);
		if(a[n] == 0){
			break;
		}
	}
}

template <int bigger,int smaller,int newSize = bigger>
bitset<newSize> subtract(bitset<bigger> a,bitset<smaller> b){
	bitset<newSize> result = 0;
	result = add<newSize,bigger,newSize> (result,a);
	for(bitset<smaller> track = 0;track != b;inc(track)){
		dec(result);
	}
	return result;
}


template <int nA,int nB>
bool lessthan(bitset<nA> a,bitset<nB> b){
	int aTotal = 0;
	int bTotal = 0;
	int aLastSet = 0;
	int bLastSet = 0;
	for(int n = 0;n < a.size();n++){
		if(a[n] == 1){
			aLastSet = n;
		}
		aTotal += a[n];
	}
	for(int n = 0;n < b.size();n++){
		if(b[n] == 1){
			bLastSet = n;
		}
		bTotal += b[n];
	}
	if(aLastSet < bLastSet){
		return true;
	}
	if(aLastSet == bLastSet){
		if(aTotal < bTotal){
			return true;
		}
		return false;
	}
	return false;
}

template <int bigger,int smaller,int newSize = bigger> 
bitset<newSize> divide(bitset<bigger> a,bitset<smaller> b){
	for(bitset<newSize> track = 0;track != a;inc<newSize>(track)){
		a = subtract<bigger,smaller> (a,b);
		if(lessthan<smaller,bigger>(b,a) ){
			inc<newSize>(track);
			return track;
		}
	}
}

template <int bigger,int smaller,int newSize = bigger>
bitset<newSize> modulo(bitset<bigger> value,bitset<smaller> modder){
	for(bitset<newSize> result = 0; ;inc<newSize> (result)){
		
	}
}

int main(){
  cout << "Hello, world!\n";
  bitset<1536> p = 0;
  bitset<1536> q = 0;
  bitset<3072> n = 0;
  bitset<1024> e = 0;
  bitset<3072> d = 0;
}

[ne555]

It also fails on gcc and clang

note: candidate template ignored: substitution failure : deduced non-type
template argument does not have the same type as the corresponding template
parameter ('unsigned long' vs 'int')

to fix, change template <int bigger,int smaller,int newSize = bigger + 1>
to template <unsigned long bigger,unsigned long smaller,unsigned long newSize = bigger + 1>

still, I don't like the different sizes.


¿what's the purpose of this exercise? perhaps you should code the functions as you were in elementary school
https://en.wikipedia.org/wiki/Long_division

your lessthan function is incorrect, you count the number of set bits (¿?)
for example, you end up saying that 0b1100 is less than 0b1011

[zapshe]

Weird that you guys got errors, I didn't get a single one on Visual Studio.

It runs fine and prints out

Hello, world!

like it should.

But yea, I don't see the point in coding it like this.

[highwayman]

@whitenite1 the default template args work for me without even a warning and I meant too big as in I would have to manually type in all of the code myself without copy and paste, otherwise yes I would have just copied and pasted, sry. Also what version of c++? Maybe I’m unintentionally using a later version, it’s supposed to be c++11 on mine, maybe your using c++98 or 03? I think I’ll test it later

@ne555 where? That looks like my add function, but I don’t under stand why it would need so much, is my n too big for it? Hm right it was supposed to avoid error by checking who last bit is bigger, but I see what you mean ok I will fix that too. It’s not an exercise per se, I just kind of felt like taking on something big, this is just part of a bigger project that requires numbers that are literally 3072 bits long as you can see from my n. It’s me trying to recreate the rsa cipher. I would do it like that(elementary long division), but that would require that I look at my numbers and could actually see my numbers in a very different way, which I’ve tried before and it’s much more complicated and unneeded for the most part. The different sizes are just me trying to save space really.

The bolded stuff is just so I remember what I’m supposed to fix.

[whitenite1]

@highwayman

Also what version of c++?

I'm using Visual Studio 2012

[zapshe]

Worked for me on Visual Studio 2019

[highwayman]

@whitenite1 I checked about the default template arguments and they still work fine in c++98 so I am really confused as to why your compiler gives you an error.



@ne555 I changed all the template args to unsigned longs just to be safe and I was thinking about it and here’s my new lessthan() func:

template <int nA,int nB>
bool lessthan(bitset<nA> leftArg,bitset<nB> rightArg){
  int leftArgTotal = 0;
  int rightArgTotal = 0;
  
  for(int i = 0;i < nA;i++){
    if(leftArg[i] == 1){
      leftArgTotal += i;
    }
  }
  
  for(int i = 0;i < nB;i++){
    if(rightArg[i] == 1){
      rightArgTotal += i;
    }
  }

  if(rightArgTotal < leftArgTotal){
    return true;
  }
  return false;
}

[highwayman]

I'm using Visual Studio 2012

Worked for me on Visual Studio 2019

So then maybe it really is a version thing?

also @zapshe didn’t see your post, I basically explain the same thing to ne555 if you look right after your post I think:

It’s not an exercise per se, I just kind of felt like taking on something big, this is just part of a bigger project that requires numbers that are literally 3072 bits long as you can see from my n. It’s me trying to recreate the rsa cipher. I would do it like that(elementary long division), but that would require that I look at my numbers and could actually see my numbers in a very different way, which I’ve tried before and it’s much more complicated and unneeded for the most part.

[deleted account xyzzy]

The C++ language versions available are quite different between the various VS versions, and how C++ source is compiled as well.

VS 2012 isn't fully C++11 compliant AKAIK, forget about C++14 or C++17.

There are several compilation differences between VS 2017 and VS 2019 even if you use the same C++ language standard.

You'd have to put a gun to my head to get me to use VS 2012. I have both VS 2017 and VS 2019 installed. They work just fine in parallel.

MS got smart in putting out the VS studio package for free with their Community editions.

[ne555]

> Worked for me on Visual Studio 2019
it "worked fine" in gcc and clang until I tried to instantiate the template functions.


the reason for the change of the template parameter from int to unsigned long (actually, it should have been size_t) it's because that's the datatype of the parameter of the bitset
template <size_t N> class bitset;
http://www.cplusplus.com/reference/bitset/bitset/


> It’s not an exercise per se, I just kind of felt like taking on something
> big, this is just part of a bigger project that requires numbers that are
> literally 3072 bits long
in that case, your code is awful, try to compute the time complexity of your functions.
for example, your add() function iterates a+b times, that's 2^3072.
think on how you did it in elementary school.


about your lessthan() function, ¿why are you adding things?
in real life, ¿how do you compare two numbers that have the same amount of digits?

[Niccolo]

@ne555

in that case, your code is awful

...that just hit me in the funny bone and I can't stop laughing...

[highwayman]

@ne555

in that case, your code is awful

why thank you, I try.
this was actually one of the reasons I couldn’t just post the stuff I wanted to post because they kinda are built on each other in a tower type thing.
My add func. Let’s see. Elementary school. Um.

template <size_t bigger,size_t smaller,size_t newSize = bigger + 1>
bitset<newSize> add(bitset<bigger> leftArg,bitset<smaller> rightArg){
  bitset<newSize> result = 0;
  for(int i = 0;i < smaller;i++){
    if(leftArg[i] & rightArg[i] == 1){
      result[i] = 0;
      for(int y = i + 1;y < bigger;y++){
        if(leftArg[y] & 1 == 1){
          break;
        }
        leftArg.flip(y);
      }
    }
    if(leftArg ^ rightArg == 1){
      result[i] = 1;
    }
  }
  for(int i = smaller;i < bigger;i++){
    result[i] = leftArg[i];
  }
  return result;
}

Why I'm adding things (the logic):

Say we have 01001011 and 01110110, how do we know which one is the bigger number? Well, there are two ways:

Number one:
You can take the binary and change it to a decimal value, look at the decimal value, and immediately know which is bigger because humans literally have a thing called instinctual math that allows us to tell.

Number two:
We can be lazy...
Let’s line them up:
01001011
01110110

Alright nice and lined up.
I can tell that the bottom one is bigger because while they both have the 6th digit on, only the second binary number has its 5th digit on.
the 6th digit has a value on its own.
So does the 5th digit.
The if you add the 5th digit’s value to the 6th digit’s value, you will get a bigger value than just the 5th or just the 6th digit by itself.


also if you add 2 + 3 it is smaller than 5 + 6.
(10 + 11 < 10000 + 100000)

That’s why my lessthan func works.

[ne555]

> humans literally have a thing called instinctual math
...

tell me what does your algorithm gives you for these cases
11
10

11000000
10111111


> I can tell that the bottom one is bigger because while they both have the 6th
> digit on, only the second binary number has its 5th digit on
¡yes!

// traverse the numbers from most significant bit (msb) to least significant bit (lsb)
for x = msb to lsb:
	if a[x] and not b[x]: //a is bigger, may also test a[x]>b[x]
		return false
	if b[x] and not a[x]: //b is bigger
		return true
return false //they are equal 

the carry part of your sum() function looks wrong,
also, ¿did you use xor in elementary school?

//for decimal numbers
carry = 0
for x = lsb to msb:
	aux = a[x} + b[x] + carry
	result[x] = aux%10
	carry = aux/10
if carry:
	result.append(carry)

[highwayman]

@ne555

tell me what does your algorithm gives you for these cases ...
11000000
10111111

I see what you mean now.. that’s too bad. :(

The carry part of my sum function is wrong, I don’t pay attention to the most important bit in it(the last one that only result has). I’ll definitely fix that, thank you. But I don’t really understand your code and how I would really use it, I can’t really wrap my head around it for whatever reason.

did you use xor in elementary school

Yes. Every day, I would walk up to the board and talk about the wonders of the exclusive or. Lol. XD
It’s just a lazy way of saying if( (leftArg[i] == 1 && rightArg[i] == 0) || (leftArg[i] == 0 && rightArg[i] == 1) ) {
//whatever
}

[highwayman]

My gosh this is the third time I’ve written this function XD. Tell me what you think. (It’s a bit different from your pseudocode)
Ok. Here we go:

template <size_t nA,size_t nB>
bool lessthan(bitset<nA> leftArg,bitset<nB> rightArg){
  int * laSet;
  int * raSet;
  laSet = new int [leftArg.count()];
  raSet = new int [rightArg.count()];
  int x = 0;
  for(int i = 0;i < nA;i++){
    if(leftArg[i] == 1){
      laSet[x++] = i;
    }
  }
  x = 0;
  for(int i = 0;i < nB;i++){
    if(rightArg[i] == 1){
      raSet[x++] = i;
    }
  }
  for(int i = 0; i < leftArg.count() < rightArg.count() ? leftArg.count() : rightArg.count();i++){
    if(leftArg[i] < rightArg[i]){
      return true;
    }
  }
  return false;
}

[keskiverto]

1. Memory leaks

2. Lines 3-18 have no effect on the result.

3. bool condition = i < leftArg.count() < rightArg.count() ? leftArg.count() : rightArg.count()
makes no sense at all

3a. a < b < c is definitely wrong way to combine binary relation operators.

3b. boolean ? number1 : number2 can return false only if chosen number is 0.

[highwayman]

1: where? Show me please.
2: um. Oops. Sry that’s supposed to be if(laSet[i] < raSet[i]) for line 20 - then it makes sense, my bad.
3: Sry that should be i < (leftArg.count < rightArg.count() ? leftArg.count() : rightArg.count())
3a: N/A
3b: Huh?? What do you mean? How?? I’m really missing something!

[Ganado]

1: where? Show me please.

Your last code before this one has you calling new[], but you don't ever call delete[] for each new[].

3: No. a < b < c is not saying "a is less than b is less than c".
You need your condition to be: a < b && b < c
[Note: I didn't actually read if this is correct logic or not, but "a < b < c" is certainly not correct.

[highwayman]

1: alright this is exactly why this is up here I almost never think about deleting because I almost never use dynamic arrays, so just before the returns I’ll put the delete[]s (post that in a sec)

3: I don’t want a < b < c, I want a < b or a < c depending on which one is smaller.