[ art / civ / cult / cyb / diy / drg / feels / layer / lit / λ / q / r / sci / sec / tech / w / zzz ] archive provided by lainchan.jp

lainchan archive - /λ/ - 20802



File: 1481810918607.png (65.07 KB, 300x105, code_quality.png)

No.20802

I've been programming c for a couple years very slowly and lately have gotten into it much more.
As a challenge i wrote a program to convert Decimal into Binary Equivalent as something like that wasn't in any libraries i could find.
What do you guys think of my code? And general critique thread.
#include <stdio.h>
#include <math.h>

int findGreater(int input){

int power = 0;

while(input >= pow(2,power)){

power++;

}

power--;
return power;

}

int main(){

int dec, greatest = 0;

printf("Value to convert: ");
scanf("%d", &dec);

if(dec < 0){

printf("Incorrect Value Type.\n");
return 1;

}

greatest = findGreater(dec) + 2;
char binary[greatest];

int size = sizeof(binary)/sizeof(char);

for(int index = 0; index <= greatest; index++){

binary[index] = '0';

}

binary[greatest - 1] = '\0';

while(dec != 0){

greatest = findGreater(dec);
binary[size - (greatest + 2)] = '1';
dec -= pow(2,greatest);

}

printf("Binary: %s\n", binary);

}

  No.20803

>>20802
Ignore the lack of tabbing, must have messed up copy pasting.

  No.20804

Too many blank lines.
It can help to make your code easy to understand in moderation, but you also want to have as much code on your screen as possible, to avoid scrolling too much.
I also don't like seeing unnecessary spaces in equalities or variable initialization, but this is more of a personal taste.

  No.20805

>>20802

See the following implementation based on
https://rosettacode.org/wiki/Binary_digits#C

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

char *tobinary(uint32_t x);

int main(void)
{
int decimal = 0;
printf("Value to convert: ");
scanf("%d", &decimal);

if(decimal < 0){
printf("Incorrect Value Type.\n");
return 1;
}

char *binary = tobinary(decimal);

printf("Binary: %s\n", binary);
free(binary);
}

char *tobinary(uint32_t x)
{
size_t bits = (x == 0) ? 1 : log10((double) x)/log10(2) + 1;
char *ret = malloc((bits + 1) * sizeof (char));
for (size_t i = 0; i < bits ; i++) {
ret[bits - i - 1] = (x & 1) ? '1' : '0';
x >>= 1;
}
ret[bits] = '\0';
return ret;
}

As far as I can determine it is 20 lines shorter and runs a little bit faster.

  No.20807

>>20802
A brief skim over your code brings me some things to mind:
At findGreater() you do
int power = 0;
/* ... */
power--;
You could've just initialize power to -1 AND add a comment as to why also
power--; 
return power;
/* Could be made more succint with */
return --power;
At main() you have:
char binary[greatest];
int size = sizeof(binary)/sizeof(char);
which is redundant.
binary is greatest*sizeof(char) and size is sizeof(binary)/sizeof(char) === greatest*sizeof(char)/sizeof(char) === greatest.
Thus size === greatest
I don't know about you, I like to keep my code succint, so that one has less noise to read against.
The algorithm itself may be correct, it is also not my favorite, just because it doesn't quite exploit the machine level representation of integers as binary numbers. I'd rather use bitwise operations.
A recursive definition would also be much shorter as well, you'd do well in looking that up.

Keep it up lainon, make us proud.

  No.20813

>>20807
OP here, the only problem with the first suggestion is that if i set power as -1, it'll take another loop to reach the number it needs and it'll still output at 1 too high.
But thanks for everything else and I'll give those a look.

  No.20818

>>20805
Excuse my ignorance, but is there a reason for the use of log10, instead of just log (base e) or log2?

  No.20824

>>20813
Oh yes I see that now, you're right

  No.20860

>>20818
Let log(a,n) be the log of n in base a (for instance, log(2,4) = log(10,100) = 2)

Then, according to math, log(a,n) = log(b,n)/log(b,a).

  No.20861

Doing it the Unix™ way.
#include <stdio.h>
#include <stdlib.h>

#include <errno.h>
#include <unistd.h>

#define ABORT(X, ...) fprintf(stderr, X, ##__VA_ARGS__); exit(1)

int computesize(int n) {
if (n == 0 || n == 1)
return 1;
else
return 1 + computesize(n/2);
}

void tobinary(int n, int fd) {
#define write0 write(fd, "0", 1)
#define write1 write(fd, "1", 1)

if (n == 0)
write0;
else if (n == 1)
write1;
else {
tobinary(n/2, fd);
if(n % 2 == 0)
write0;
else
write1;
}
}

int main(int argc, char** argv) {
int fildes[2];
int bsize, n, r = 0;
char *buf;

if (argc != 2) {
ABORT("usage: ./a.out number\n");
}
errno = 0;
n = atoi(argv[1]);
if (errno != 0) {
ABORT("error: %s is not a valid input (should be an int).\n", argv[1]);
}

bsize = computesize(n);
buf = (char *) malloc(bsize);

if (pipe(fildes) == -1) {
ABORT("error: an error occured while creating the pipe.\n");
}
switch (fork()) {
case -1:
ABORT("error: an error occured while forking the program.\n");

case 0: /* Child - writes to pipe */
close(fildes[0]); /* Read end is unused */
tobinary(n, fildes[1]);
close(fildes[1]); /* parent will see EOF */
return 0;

default: /* Parent - reads from pipe */
close(fildes[1]); /* Write end is unused */
while (r != bsize)
r += (int) read(fildes[0], buf+r, bsize-r); /* Get data from pipe */
/* At this point, a further read would see end of file ... */
close(fildes[0]); /* Finished with pipe */
}

printf("%s\n", buf);
return 0;
}

  No.20862

>>20860
Ok. But the code had log10(x)/log10(2)

I wondered why use base 10? Why not log(x)/log(2)

Or, as I see now, the equivalent log2(x)

  No.20863

>>20862
Oh whoops, it seems log2() is C++11 and not in C. But still, my question stands, why not log(x)/log(2)?

  No.20866

>>20861
W... why?
(btw, are #define's scoped to blocks? I thought they had static scoping)>>20861

  No.20867

>>20866
>(btw, are #define's scoped to blocks? I thought they had static scoping)
Let me answer to this myself: it's literal substitution done by the preprocessor, so it's not a matter of scoping but of everything that comes in subsequent lines in the source file.

Then the point I wanted to make stands: it's misleading to put a macro definition inside a block of code unless you #undef it where the block ends.

  No.20871

>>20861
That looks awful. Why a fork and a pipe?
That's not "The UNIX Way", that's more like the GNU way or something.
Ideally in Unix you KISS (In practice, though, it gets plagued with #ifdef's)

  No.20933

Just to clarify, not op: All this arguing is why im reluctant to get into coding.

  No.20957

>>20863

I am not sure why the Rosetta Code example used log10 instead of log, the code works fine with either.

I assume for clarity of understanding, as the performance of log10 vs log is compiler and architecture dependent.

  No.20972

>>20818
log10 is useful because of the property that logs have. log10 of a divided by log10 of b would result in logb(a)

  No.20973

>>20972
that property is true for any log:

LogX(a)/LogX(b) = Logb(a) for any X > 1

  No.20993

File: 1482327351908.png (493.66 KB, 200x174, 1481426825653.png)

>>20933
None of us are trying to get you to code.

  No.21027

int findGreater(int input){

int power = 0;
int test = 2;

while(input >= test){
test = test << 1;
power++;

}

power--;
return power;

}

Wouldn't this work too?

  No.21041

>>20802
This is how I would write that first function:
int
find_greater(int input)
{
int power = 0;

while (input >= (power * power))
power++;

return power-1;
}
Do note that I put the brace on the same line with a space separating the closing paren of a condition, e.g.:
if (foo) {
bar();
}

  No.21045

power ** 2 != 2 ** power

int
findGreater(int input) // returns n such that input has (n-1) digits
{
int power = 2, foo = 2;

while (input >= foo) {
foo <<= 1;
power++;
}

return power;
}

and in the code, the line that set greatest is '''greatest = findGreatest(dec);'''

  No.21228

>>20802
>mixing algorithm and interface
void dec2bin(int dec, char *bin)
{
for (; dec; dec >>= 1)
*bin++ = dec & 1 - '0';
*bin = '\0';
}

int bin2dec(char *bin)
{
int dec = 0;
while (*bin)
dec = dec << 1 + *bin++ - '0';
return dec;
}

  No.21259

>>20861

>using forking to convert decimal and binary


In other news man found using chainsaw to trim his grass.

  No.21260

>>21041
You misunderstood the purpose of Op's find greater function.

2^N != N^2

>>21045
I don't think that foo <<= 1 is the solution you want here actually

  No.21261

>>20933
go read "Hackers and Painters" by Paul Graham. After that you will know if you want to code or not

  No.21298

>>21228
wtf is that piece of soykaf
It doesn't even work.

  No.21330

>>20933
you will never get into coding because of your perception of these deliberations

  No.21345

File: 1484010056088.png (688.68 KB, 200x160, 1470483671584.png)

>>20802
>What do you guys think of my code?
Too much unnecesary code. Here is mine:
#include <stdio.h>
#include <stdlib.h>

int main()
{
int n, i;
scanf("%d", &n);
for(i = -1 + sizeof(int) * 8; i >= 0 ; i--)
printf("%d", (n >> i) - 2 * (n >> (i + 1)) );
printf("\n");
return 0;
}
It should work, however, it seems C compiler does not allow a right bitwise operation when the right operand equals sizeof(int)*8. Anyone know why?

  No.21346

>>21345
imo it's implementation-specific, because the x86/x64 assembly SAR (shift arithmetic right) instruction (as well as all the other shift instructions) works that way.

  No.21347

>>21345
I fixed your code :3.

#include <stdio.h>

int main()
{
int n, i;
scanf("%d", &n);
for(i = -1 + sizeof(int) * 8; i > 0 && (n >> i & 1) == 0; i--);
for(; i >= 0 ; i--)
putchar((n >> i & 1) + '0');
puts("\n");
return 0;
}

  No.21386

>>21347
Great code, anon. Here is my version of the binary to decimal conversion:
#include <stdio.h>

int main()
{
char n[32];
int i, k;
unsigned int d = 0;
scanf("%s", n);
for(i = 0; n[i] != '\0' && i < 32; i++)
n[i] -= '0';
for(k = 0; i > 0; i--)
d |= (n[i - 1] << k++);
printf("%u\n", d);
return 0;
}
Is there an easy way to do this using int instead of a char array?

  No.21633

File: 1485404579878.png (64.69 KB, 195x200, tumblr_nejkb9efbi1qazmoxo1_500.jpg)

I'm a noob, I made a prime number tester that has the user input a number, is it trash?
#include <stdio.h>

int a;

int main(void){

puts("input a number");
scanf("%d",&a);

//DUMB GLUE FOR NAUGHT AND TWO (ーー;)
if(a==2){
printf("is prime");
return 0;
}
else if(a==1||a==0){
printf("its not prime");
return 0;
}
//DUMB GLUE FOR NAUGHT AND TWO (ーー;)

for(int i=2; i<= a - 1; i++){ //start i at 2 because x % 1 == x for all nonzero x. everything divides by 1. shame this doesnt work on 2 without affixing IF 2 ISPRIME as above
if(a % i == 0){ //maybe add something like "...||i>a/2" to the condition?
printf("its not prime");
return 0;
}
}
printf("is prime");
return 0;

}

  No.21634

why dont one of you lains use your c knowledge to make a gui for cjdns https://github.com/cjdelisle/cjdns making it easier for other lains to just lainnet

  No.21636

>>21633
It's okay. It's only naive, you could do a couple things for performance:
For any composite (not prime) number N where N = a*b, either a <= sqrt(N) or b <= sqrt(N) (or both).
So you only need to look up to sqrt(N), which reduces the workload
Half of the times you add 1 to `i' in your code, you're implicitly dividing by 2*k where you'd already divided by both 2 and k, so after i==3 I'd do i+=3.

And the check for a==2 is redundant with a%i in the for loop because it starts at 2. I read the comment and I don't understand why it wouldn't work with an input of 2, care to explain?
Also (a==0||a==1) can be replaced with (a<2), saves you a couple cycles.

  No.21639

>>21636
I didnt know about the square root thing, interesting
2 % 2 is 0, which'd cause it to print "not prime", but 2 is prime isnt it?

  No.21642

>>21633
Implementing the Sieve of Eratosthenes is the usual way to write a relatively efficient prime number tester.

  No.21643

>>21633
You have an integer overflow bug in your code. Think about what would happen if the entered number is larger than INT_MAX.

You can see this by adding a printf("num = %d\n",a) after the scanf call.

  No.21646

>>21643
Yeah, I knew that'll happen, I didnt try to make it work for arbitrarially large numbers.
Perhaps I'll try to do said "sieve of eratosthenes" with arbitrarially large numbers a bit later, if its not beyond me right now.

  No.21965

File: 1486672361191.png (77.31 KB, 200x150, kag.jpg)

>>21642
having just done sieve of ef eratosthenes, why would you do all of that just to test if a single number was prime, rather than to generate a list of all primes smaller than it only? Would it really be more efficientr than an optimized naiive prime tester?
I imagine youd do it like,
#include <stdio.h>

//for input number 'n' and an array arr[n], where 1 is treated as prime and 0 as composite

for(int i=2;i<n;i++){
if(arr[i]{
for(int m=i*i;m<=n;m+=i){
arr[m]=0
if(!arr[n]){
printf("Is not prime);
}
}
}
}
to see if its not prime, but then you have to do every number up to it to see if it is prime.
Would that still be more efficient than using a naiive thing to check up to its square root?

  No.21967

>>21965
>having just done sieve of ef eratosthenes, why would you do all of that just to test if a single number was prime, rather than to generate a list of all primes smaller than it only? Would it really be more efficientr than an optimized naiive prime tester?
It's possible.

>Would that still be more efficient than using a naiive thing to check up to its square root?

The most efficient way to test the primeness of a number that I can currently think of would be to generate a hash table of primes and then check for the number as a key. That turns the operation from O(n) to O(1), assuming a good hash table, at the expense of space.

If I had to do this for a serious system, I'd generate as many primes as the system would need to test for or as many as I could fit within the space requirements if there wasn't a limit.

  No.21970

>>21967
>The most efficient way to test the primeness of a number that I can currently think of would be to generate a hash table of primes and then check for the number as a key.

https://en.wikipedia.org/wiki/AKS_primality_test

  No.21994

>>21970
It's true that generating those primes would make this method pretty slow when the program generates the first time, they could be written to file and loaded next time. The number of primes could be expanded like a dynamic array too. This is assuming a problem where running it once isn't a big deal, but having it run fast afterwards is a big deal. AKS primality test is not O(1), table lookup is. (Well, technically is only O(n) worst case but in practice would almost certainly be constant. O(n) is still better than a primality test, a known "hard" problem in this sense! It's polynomial, as your link states.)

  No.22021

>>21994
that works until you get into very large numbers, like the ones that are useful for cryptography. There are many more than a trillion primes below 2^2048.

Basically, when you use a table you trade space for speed. That is not the best solution in many cases.

  No.22297

// compute n/m
int bindiv(unsigned int n, unsigned int m) {
if (n < m)
return 0;
int x = 2*bindiv(n/2, m);
return n - x*m >= m ? x+1 : x;
}

Just for the algorithmic sake, here is integer division by dichotomy.

  No.22376

>>21298
interesting. it nearly works.
  #include <stdlib.h>
#include <stdio.h>

void dec2bin(unsigned int dec, char *bin)
{
for (; dec; dec >>= 1)
*bin++ = (dec & 1) + '0';
*bin = '\0';
}

int bin2dec(char *bin)
{
unsigned int dec = 0;
while (*bin)
dec = (dec << 1) + *bin++ - '0';
return dec;
}

int main () {
char buf[33] = {0};
dec2bin(0x7001F00F, buf);
printf("dec2bin(0x8001F00F) => %s\n", buf);
printf("bin2dec(0xFF81000F) => %x\n",
bin2dec("1111" "1111" "1000" "0001" "0000" "0000" "0000" "1111"));
return 0;
}

output:

  dec2bin(0x8001F00F) => 1111000000001111100000000000111
bin2dec(0xFF81000F) => ff81000f

original fails on 'negative' numbers, with dec2bin even going into an infinite loop. dec2bin produces reversed output.

and then the original had errors like, - instead of + '0' in dec2bin, and a completely wrong bin2dec without those parens.

  No.22377

>>22376
missing last 1 in output is my error, I'd temporarily changed the number to 0x7001F00F

  No.22381

>>22376

fam this is beautiful c but (amd I'm a stickler) I don't like if and loops on single lines I personally prefer to enclose them in braces. This is just a personal preference though and I think your code has a real clean beauty to it. Nice job!

  No.22448

File: 1489169087422.png (96.22 KB, 200x33, Screen Shot 2017-03-10 at 10.03.26 AM.png)

Hey friends. I'm doing Project Euler (it's been taking over my life. I need help), and I'm running into a small problem in implementing a struct in C++:

  #include <iostream>
struct Index
{
int xInd, yInd;
Index(int x, int y)
{
this->xInd = x;
this-> yInd = y;
}

bool operator<(const Index& rhs)
{
return (this->xInd < rhs.xInd);
}
std::ostream& operator<<(std::ostream& out)
{
out << "( " << this->xInd << ", " << this->yInd << ")\n";
return out;
}

};
int main()
{
Index i(6, 10);
std::cout << &i;
return 0;
}

When I run this code in XCode, I get the following error:
  .../usr/include/c++/v1/__functional_base:63:21: Invalid operands to binary expression ('const Index' and 'const Index') 

I'm not sure how cout-ing is an invalid binary expression when I've clearly defined it in the struct's "<<" operator... Thoughts?

  No.22452

>>22448
Found the issue:

apparently binary operators need to be 'friend' non-member functions.

  No.22476

>>22448
>defining functions in a structure
wat the fug, c++