A story about writing a ratio calculation at an in-house study session

Introduction

I think there are situations where the value is changed while maintaining the ratio, such as enlarging / reducing the image. This time, assuming such a situation, I tried to solve the following problems together with young employees. By the way, if you search the net, the answer will come out, so I prohibited the net search.

problem

1. Find the ratio of two integer values x, y
2. Find the scaled value with the larger of x and y as the maximum value max.

Solution 1: Division

First of all, the easiest method was to find the ratio using a simple division method.

Example.

x = 100
y = 10
x / y = 10
x is 10 times y
That is, x:y=10:1

I think it's intuitive and straightforward, but it has the disadvantage of losing accuracy when it's not divisible by this method.

Example.

x = 100
y = 30
x / y = 3.3333...
Is x about 3 times y?

In this case, "x: y = 10: 3" should be fine, but with the ratio obtained by using a simple division, there is a problem that y does not become 150 when max is set to 500 in the following problem. It will occur. I think it is ant to deal with rounding depending on the tolerance of the error.

• In some cases, it can be handled by reversing the calculation, but it is omitted as an example.

Solution 2: Greatest common divisor

Next, as a solution prepared in advance, I presented a method to find the ratio by dividing each of x and y by the greatest common divisor.

Example.

x = 100
y = 30
Greatest common divisor= 10
x : y = x /Greatest common divisor: y /Greatest common divisor
That is, x:y=10:3

With this method, you will be able to calculate the ratio as an integer.

Euclidean algorithm

As a method of finding the greatest common divisor, "[Euclidean algorithm](https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%" AA% E3% 83% 83% E3% 83% 89% E3% 81% AE% E4% BA% 92% E9% 99% A4% E6% B3% 95) ”.

To summarize briefly, the following procedure will be repeated.

1. Divide the large value by the small value
2. If there is a remainder, divide the original small value by the remainder that came out.

Recursion and loop

There are two ways to write iterative processes: recursion and loops. Recursion can cause stack overflow, but you can write clean code. Loops, on the other hand, can be redundant code and can lead to poor visibility when conditions become complex. Also, be aware that if you make a mistake in the conditions for exiting both, you will end up in an infinite loop.

• I will not write in detail about recursive stack overflow.

Tail call optimization

In modern languages, recursive stack overflow may be resolved by tail call optimization. However, since this is a language (compiler) function, it does not solve any language, so please consider it when considering the implementation.

In this case

Only in Kotlin, but [Fibonacci number](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3% I tried to confirm using 83% 83% E3% 83% 81% E6% 95% B0).

val x = 1836311903
val y = 1134903170

The above is the combination of the maximum and maximum Fibonacci numbers that can be specified as an Int, and even when using this, the number of trials was only 45. Therefore, in this case, it turns out that recursion and loops can be used without any particular consciousness.

However, recursion when thinking on an actual project basis is an idea. For teams with various levels of understanding of the program, from young to veteran, isn't it easier to understand loops at any level in simple iterative processing like this problem? It was concluded. Of course, if it gets complicated, it will be difficult to understand even in a loop, so it is necessary to consider ways to improve readability, including recursion.

Code example

The following is the code that rewrites this problem so that it is easy to compare what was written in each language.

• The answer to question 2 may have an error, but I think that the handling will differ depending on the case, so the code is not particularly addressed.

Kotlin

fun main(args: Array<String>) {
  val x = 30
  val y = 100
  val max = 500

  val gcdResult = gcd(x, y)
  val xRatio = x / gcdResult
  val yRatio = y / gcdResult
  println("Greatest common divisor: $gcdResult => $xRatio:$yRatio")
  
  val largeResult = max
  val smallResult = getSmallerGcdPair(x, y, largeResult)
  if(x > y) {
    println("$x:$y => $largeResult:$smallResult")
  } else {
    println("$x:$y => $smallResult:$largeResult")
  }
}

fun gcd(xInput: Int, yInput: Int): Int {
  var largeVal = Math.max(xInput, yInput)
  var smallVal = Math.min(xInput, yInput)
  var remVal = 0

  do{
    remVal = largeVal % smallVal
    largeVal = smallVal
    smallVal = remVal
  } while(remVal > 0)

  return largeVal
}

fun getSmallerGcdPair(xRatio: Int, yRatio: Int, largeResult: Int): Int {
  var largeRatio = Math.max(xRatio, yRatio)
  var smallRatio = Math.min(xRatio, yRatio)

  return largeResult / largeRatio * smallRatio    
}

Swift

func main() {
  let x: Int = 30
  let y: Int = 100
  let max = 500

  let gcdResult = gcd(x, y)
  let xRatio = x / gcdResult
  let yRatio = y / gcdResult
  print("Greatest common divisor: \(gcdResult) => \(xRatio) : \(yRatio)")

  let largeResult = max
  let smallResult = getSmallerGcdPair(xRatio, yRatio, largeResult)
  if(x > y) {
    print("\(x):\(y) => \(largeResult):\(smallResult)")
  } else {
    print("\(x):\(y) => \(smallResult):\(largeResult)")
  }
}

func gcd(_ xInput: Int, _ yInput: Int) -> Int {
  var largeVal = max(xInput, yInput)
  var smallVal = min(xInput, yInput)
  var remVal = 0

  repeat {
    remVal = largeVal % smallVal
    largeVal = smallVal
    smallVal = remVal
  } while remVal > 0

  return largeVal
}

func getSmallerGcdPair(_ xRatio: Int, _ yRatio: Int, _ largeResult: Int) -> Int {
  let largeRatio = max(xRatio, yRatio)
  let smallRatio = min(xRatio, yRatio)

  return largeResult / largeRatio * smallRatio
}

main()

PHP

<?php
const x = 30;
const y = 100;
const max = 500;

define('gcdResult', gcd(x, y));
define('xRatio', x / gcdResult);
define('yRatio', y / gcdResult);
echo "Greatest common divisor: ".gcdResult." => ".xRatio.":".yRatio.PHP_EOL;

const largeResult = max;
define('smallResult', getSmallerGcdPair(xRatio, yRatio, largeResult));
if(x > y) {
  echo x.":".y." => ".largeResult.":".smallResult.PHP_EOL;
} else {
  echo x.":".y." => ".smallResult.":".largeResult.PHP_EOL;
}

function gcd($xInput, $yInput): int {
  $largeVal = max($xInput, $yInput);
  $smallVal = min($xInput, $yInput);
  $remVal = 0;

  do {
    $remVal = $largeVal % $smallVal;
    $largeVal = $smallVal;
    $smallVal = $remVal;
  } while($remVal > 0);
  
  return $largeVal;
}

function getSmallerGcdPair($xRatio, $yRatio, $largeResult): int {
  define('largeRatio', max($xRatio, $yRatio));
  define('smallRatio', min($xRatio, $yRatio));

  return $largeResult / largeRatio * smallRatio;
}

JavaScript

function main() {
  const x = 30
  const y = 100
  const max = 500

  const gcdResult = gcd(x, y)
  const xRatio = x / gcdResult
  const yRatio = y / gcdResult
  console.log(`Greatest common divisor: ${gcdResult} => ${xRatio} : ${yRatio}`)

  const largeResult = max
  const smallResult = getSmallerGcdPair(xRatio, yRatio, largeResult)
  if(x > y) {
    console.log(`${x}:${y} => ${largeResult}:${smallResult}`)
  } else {
    console.log(`${x}:${y} => ${smallResult}:${largeResult}`)
  }
}

const gcd = (xInput, yInput) => {
  let largeVal = Math.max(xInput, yInput)
  let smallVal = Math.min(xInput, yInput)
  let remVal = 0

  do {
    remVal = largeVal % smallVal
    largeVal = smallVal
    smallVal = remVal
  } while(remVal > 0)

  return largeVal
}

const getSmallerGcdPair = (xRatio, yRatio, largeResult) => {
  const largeRatio = Math.max(xRatio, yRatio)
  const smallRatio = Math.min(xRatio, yRatio)

  return largeResult / largeRatio * smallRatio
}

main()

Java

import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    final int x = 30;
    final int y = 100;
    final int max = 500;

    final int gcdResult = gcd(x, y);
    final int xRatio = x / gcdResult;
    final int yRatio = y / gcdResult;
    System.out.println("Greatest common divisor: " + gcdResult + " => " + xRatio + " : " + yRatio);

    final int largeResult = max;
    final int smallResult = getSmallerGcdPair(x, y, largeResult);
    if(x > y) {
      System.out.println(x + ":" + y + " => " + largeResult + ":" + smallResult);
    } else {
      System.out.println(x + ":" + y + " => " + smallResult + ":" + largeResult);
    }
  }

  private static int gcd(int xInput, int yInput) {
    int largeVal = Math.max(xInput, yInput);
    int smallVal = Math.min(xInput, yInput);
    int remVal = 0;

    do {
      remVal = largeVal % smallVal;
      largeVal = smallVal;
      smallVal = remVal;
    } while(remVal > 0);

    return largeVal;
  }

  private static int getSmallerGcdPair(int xRatio, int yRatio, int largeResult) {
    final int largeRatio = Math.max(xRatio, yRatio);
    final int smallRatio = Math.min(xRatio, yRatio);

    return largeResult / largeRatio * smallRatio;
  }
}

Compare the code

Since it is a simple code, I think that you can read it without being aware of it even in a language that you are not usually involved with. Certainly there are habits of writing in each language, but conversely, the difference seems to be that much.

Summary

--There are cases where the exact ratio cannot be obtained by simple division. --You can find the integer ratio by using the greatest common divisor. --Loops are easier to understand than recursion --If it gets complicated, consider improving readability including recursion. ――If you read it in a language that you don't usually relate to, you may be able to understand it easily.

bonus

Only Kotlin, but I will write a recursive way to get the greatest common divisor.

gcd(Math.max(x, y), Math.min(x, y))
tailrec fun gcd(largeInput: Int, smallInput: Int): Int 
  = if(smallInput == 0) largeInput else gcd(smallInput, largeInput % smallInput)