Filip Koprivec jO-Osko

Evklidov algoritem

Evklidov algoritem je učinkovit algoritem za izračun največjega skupnega delitelja dveh števil in ga označimo z gcd(a,b), kjer predpostavimo, da a >= b. Na kratko ga lahko opišemo kot:

gcd(a,0) = a
V nasprotem primeru zapišemo a kot: a = b*q + r. gcd(a,b) je v tem primeru enak kot gcd(b, r). Vidimo, da po nekaj časa bo r = 0 in to bo končni rezultat.

Implementiraj funkcijo gcd(a,b), ki vrne največji skupni deljitelj števil a in b. Poskrbi, da bo funkcija delovala pravilno, tudi če uporabnik poda argumenta v poljubnam vrstnem redu.

Primeri: gcd(15, 5) = gcd(5, 15) = 5, gcd(1234, 23456), gcd(12, 56) = 4, gcd(14, 21) = 7

Keybase proof

I hereby claim:

I am jo-osko on github.
I am j00sko (https://keybase.io/j00sko) on keybase.
I have a public key ASCRfzaqktPSkQ_ubPT57r0dq1JsSRcByseVUjAYwJKYiwo

To claim this, I am signing this object:

Benchmark availability

	module type Number = sig
	type t

	val add : t -> t -> t
	val sub : t -> t -> t
	val mul : t -> t -> t
	val div : t -> t -> t

	val zero : t
	val one : t

	N = 100000000
	import time
	x = 0
	t = time.time()
	for j in range(0, N):
	# 1, 2, 3, 4, 5, 6, ......
	if j % 3 == 0:
	x += j
	elif j % 5 == 0:
	x += j

	"label": "OCaml",
	"type": "shell",
	"command":
	"C:\\OCaml64\\usr\\local\\bin\\ocaml-env.exe exec -- C:\\OCaml64\\home\\???\\.opam\\4.11.1+mingw64c\\bin\\ocaml.exe -init \\\"${file}\\\""

	import random

	def seed():
	random.seed(2021)

	def prazna_mreza(w, h):
	return [
	[0 for j in range(w)] for _ in range(h)
	]

	{
	"dependencies": {
	"ocaml": "4.12.x",
	"@opam/ocaml-lsp-server": "*",
	"@opam/ocamlfind-secondary": "*",
	"@opam/reason": "*"
	}
	}

	from typing import List

	from web3 import Web3
	import eth_abi


	def submit_price_hash(ftsoIndices: List[int], prices: List[int], random: int, address: str) -> str:
	assert len(ftsoIndices) == len(prices)
	assert list(sorted(ftsoIndices)) == ftsoIndices and len(set(ftsoIndices)) == len(ftsoIndices), "Indices are non increasing"
	return Web3.keccak(eth_abi.encode_abi(