Folding a paper

[yabi2943993]

Hi!
My program should read multiple lines each of two integers, h and x. H is the thickness of the paper in micrometers and x the height I want to reach by folding this paper.

#include <iostream>
main(){
    int h=0,x=0,a=0;
    while(std::cin>>h && std::cin>>x){
        a=0;
        while(h<x*1000000){h+=h;a++;}
        std::cout<<a<<"\n";}
    return 0;}

This code works but takes a lot of time to execute. How could I simplify this code or the algorithm in a way, in which the time is lower? Maybe the problem is the multiplication with 1000000?

[jonnin]

every time you fold paper, its twice as thick as it was. if you fold it 3 times, its 8x as thick.

multiply costs 1 cpu instruction, no matter the size, its not a iterative adder ;)

so, the thickness you need is tied to the lg vs number of folds. you don't even need to loop.
I think its just this (I assume you fold until you reach or exceed the desired height, and do not allow partial folds?) or do you want it exactly? To get it exactly, take the +1 off and repeat on the remainder by folding a second sheet... until happy... which you can also compute directly. there will be times when you want an x that is between something way too low and way too big if you do it integer-wise where each tick of the int = 1 fold...

double h,x, tmp;
h = 2.3; x = 37;
cout << (int(log2(x/h)+1)) << endl;

[dutch]

It's a math problem.
You want n such that h * 2**n >= x (where ** means exponentiation and h,x,n are positive integers).
So you want the integer n where 2**n >= x / h
Therefore n = ceil(log2(x / h))

(I'm assuming that x is also in micrometers since you didn't say.)

#include <iostream>
#include <cmath>

int main() {
    int h = 0, x = 0;
    while (std::cin >> h >> x) {
        // x *= 1000000; // if x is in meters
        int n = std::ceil(std::log2(double(x) / h));
        std::cout << n << '\n';
    }
}

You didn't mention any constraints, but if x needs to be multiplied by 1000000 then the above assumes x is <= ~2000 (and 32-bit ints, minimum).

[yabi2943993]

a is the output, which should say, how many times I have to fold a paper

[jonnin]

yea we get that, but what do you want it to do when you can fold it say 4 times and get 16 height (for 1 thick paper) or 5 times and get 32 height, but you wanted 25?

[dhayden]

You're probably overflowing the size on an int. Try making h and x doubles. Also print their values in the loop.

[againtry]

@yabi
I guess this is what you have in mind instead of your characteristically almost unintelligible code. The calculation is so fast, wasting time on alternative algorithms is just that - a waste of time. You might like to consider improving your coding style. Most employers would welcome it.

Working in microns (therefore some form of integer) is something for the calculation leaving the conversions for the interface alone, if necessary.

#include <iostream>

int main()
{
    uint64_t ht_req = 0, paper_thickness = 0, no_folds = 0, no_thicknesses = 0;
    
    while
        (
         std::cout << "Enter height required (microns): " &&
         std::cin >> ht_req &&
         std::cout << "Enter thickness (microns): " &&
         std::cin >> paper_thickness
         )
    {
        no_folds = 0;
        no_thicknesses = 1;
        while(paper_thickness * no_thicknesses < ht_req)
        {
            no_folds++;
            no_thicknesses *= 2;
        }
        std::cout << no_folds << '\n';
    }
    
    return 0;
}

[againtry]

I also guess the pink coloration means @yobo has no plans in the future for coming up with any advancement on its currently primitive lower-third-world coding style.

[againtry]

I should be reported. Quite right! It's not even 4th-world standard.