Count the squares

Question

Challenge

Origami (folding paper) is a creative form of art. As far as I know, master of Origami prefers square paper. Let's start from beginning - convert a rectangular paper to a square one.

So the paper is divided into squares. We remove the biggest square which shares one shorter edge with the current shape, step by step (see the picture below). And if the remaining part after one step is less or equal than 0.001 * (area of the original paper), the paper cannot be divided any further. It is possible that nothing remains at last.

Your task is to calculate how many squares are made during the process. The square in the last step that makes the paper unable to be divided is counted into the output.

Example (a paper of 1.350 width/height), output is 10:

Input and Output

Input: width / height ratio for the rectangular paper, one decimal (or an integer without the dot) from 1.002 to 1.999 with a minimal step of 0.001. You may also use any other reasonable format describing the ratio. Just mention it in your answer.

Output: square count, one integer.

Example I/O

A mapping format is used to keep the page tidy, while your code doesn't need to support a list input nor to be a mapping function.

1.002 => 251
1.003 => 223
1.004 => 189
1.005 => 161
1.006 => 140
1.007 => 124
1.008 => 111
1.009 => 100

List of all answers

Thanks to @LuisMendo, here is the graph of answers.

Remarks

• This is a code-golf so shortest code wins
• Pay attention to standard loopholes
• It's your freedom to decide how to deal with input and output but they should follow standard restrictions.

By the way...

• Comment if you have anything unclear about the challenge
• Personally I would suggest your answer contains a explanation if you are using a golfing language
• Thanks to @GregMartin, read his answer for a good mathematical explanation for the challenge.

Example Code

Here is a ungolfed version of C++ code:

#include <iostream>
#include <utility>

int f (double m)
{
    double n = 1, k = 0.001;
    int cnt = 0;
    k *= m;                       // the target minimum size
    while(m*n >= k)
    {
        m -= n;                   // extract a square
        if(n > m)
            std::swap(n, m);      // keep m > n
        ++ cnt;
    }
    return cnt;
}

int main()
{
    double p;
    std::cin >> p;
    std::cout << f(p);
    return 0;
}

All calculations related in the example code need an accuracy of 6 decimal digits, which is covered in float.

Answer 1

Haskell, 71 70 65 63 62 61 58 56 bytes

Thanks to @xnor for a some ingenious improvements!

(n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1
n!m=n#m$n*m

Try it online!

Answer 2

JavaScript (ES6), 59 58 bytes

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

Test

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

console.log(f(1.002))
console.log(f(1.003))
console.log(f(1.004))
console.log(f(1.005))
console.log(f(1.006))
console.log(f(1.007))
console.log(f(1.008))
console.log(f(1.009))

Answer 3

Mathematica, 64 53 bytes

({t=1,#}//.{a_,b_}/;1000a*b>#:>Sort@{++t;a,b-a};t-1)&

An imperative (C-style) solution is exactly the same length:

(For[t=a=1;b=#,1000a*b>#,If[a>b,a-=b,b-=a];++t];t-1)&

Answer 4

MATL, 19 bytes

`SZ}y-htG/p1e-3>}x@

The input is an array with the two numbers defining the original ratio, such as [1, 1.009]. (It is not necessary that the numbers be sorted or that one of them be 1.)

Try it online!

Explanation

`        % Do...while loop
  S      %   Sort array. Takes 1×2 array as input (implicit) the first time
  Z}     %   Split array into its 2 elements: first the minimum m, then the maximum M
  y      %   Duplicate m onto the top of the stack. The stack now contains m, M, m
  -      %   Subtract. The stack now contains m, M-m
  h      %   Concatenate into [m, M-m]. This is the remaining piece of paper
  t      %   Duplicate
  G/     %   Divide by input, element-wise
  p      %   Product of array. Gives ratio of current piece's area to initial area
  1e-3>  %   True if this ratio exceeds 1e-3. In that case the loop continues
}        % Finally (execute after last iteration, but still within the loop)
  x      %   Delete last piece of paper
  @      %   Push current loop counter. This is the result
         % End (implicit)
         % Display (implicit)

Answer 5

C (GCC/Clang), 61 59 bytes

c,k;f(m,n){for(k=m*n;m*n/k;m>n?(m-=n):(n-=m))++c;return c;}

Input is two integers (width & height) without dot, such as f(1999,1000).

I hope someone could save one byte pushing C into the 58-byte club. ;)

Answer 6

C, 59 bytes

s,a,n=1e3;C(m){for(a=m;m*n>a;s++)m>n?m-=n:(n-=m);return s;}

Try It online

The input is an integer which is the width / height ratio in thousandths (eg. 1002 for 1.002:1).

Ungolfed version

int C(int m)
{
    int n = 1000;
    int a = m;
    int s = 0;

    while (m * n > a)
    {
        if (m > n)
            m -= n;
        else
            n -= m;

        s++;
    }

    return s;
}