Mathamatics help please! - GameCreators Forum

Author

Message

Scraggle

Moderator

21

Years of Service

User Offline

Joined: 10th Jul 2003

Location: Yorkshire

Posted: 20th Feb 2018 11:51 Edited at: 20th Feb 2018 12:11

Link

Hey,

I have a functional function but it is ugly and uses two loops.
I'm pretty sure there must be an elegant mathematical way to achieve what I'm trying to achieve.

Here is the function:

+ Code Snippet

function GetNearest(d, w)
	if mod(w, d) = 0 then exitfunction d
	
	for up = d to w
		if mod(w, up) = 0 then exit
	next up
	
	for down = d to 0 step - 1
		if mod(w, down) = 0 then exit
	next down
	
	if abs(d-up) > abs(d-down) then exitfunction down
endfunction up

What it does is return the closest value of d that goes into w without a remainder.
It works, but using two loops is ugly!
There has to be a better way - anyone want to show off and help me out?

For example
Assuming w = 1000
if d = 195 then 200 will be returned
if d = 205 then 200 will be returned
if d = 240 then 250 will be returned

Animation Station - WIP
Happy Flapper
Additional Image Functions (9 sprite slicing etc.)
Additional String Functions
XML read, write, parse
Black theme for Geeny
RGB->HSV->RGB
SpriteSheet XML Control

Back to top

Profile PM Email

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 20th Feb 2018 12:25

Link

my team mate brain said something like this

+ Code Snippet

a as float
b as float
c as float

do

	a = 16
	b = 5
	c = a-mod(a,b)

	print(c)

	a = 9
	b = 5
	c = a-mod(a,b)

	print(c)
	
	if GetPointerPressed() then exit
	
	Sync()
loop

End

AGK (Steam) V2017.12.12 : Windows 10 Pro 64 Bit : AMD (17.12.1) Radeon R7 265 : Mac mini OS High Sierra (10.13)

Back to top

Profile PM Email

Scraggle

Moderator

21

Years of Service

User Offline

Joined: 10th Jul 2003

Location: Yorkshire

Posted: 20th Feb 2018 12:31

Link

I appreciate you input Markus, thank you but I don't think you understood the problem fully.
Your code doesn't do the same as mine.
The function I have written works perfectly, I just don't like using the loops and I'm pretty sure there must be a more elegant way to do it.

Animation Station - WIP
Happy Flapper
Additional Image Functions (9 sprite slicing etc.)
Additional String Functions
XML read, write, parse
Black theme for Geeny
RGB->HSV->RGB
SpriteSheet XML Control

Back to top

Profile PM Email

easter bunny

12

Years of Service

User Offline

Joined: 20th Nov 2012

Playing: Dota 2

Posted: 20th Feb 2018 12:51 Edited at: 20th Feb 2018 13:09

Link

I think this should work, ~~I can't think of any circumstances where it won't~~:

+ Code Snippet

function GetNearest(d, w)
    temp=round(w/d)
    temp=w/temp
endfunction temp

I'll write a quick program to test it on a bunch of different variables and see if it works consistently and get back to you with the results

Edit: never mind, getting some bugs. For example round(100/3)=33, then round(100/33)=3 which is the result, but it is NOT a factor. Gonna experiment with some recursion now

Edit2: I think the only way is by calculating all the divisors of the number

My Games - Latest WIP - My Website: Immortal.Digital - FB - Twitter
130,000 installs with AppGameKit and counting

Back to top

Profile PM Email

Scraggle

Moderator

21

Years of Service

User Offline

Joined: 10th Jul 2003

Location: Yorkshire

Posted: 20th Feb 2018 13:09

Link

Here's my test code with along with the function

+ Code Snippet

test = 500

do
	if GetPointerPressed()
		test = random(1, 999)
	endif
	print(str(test) + ": "+str(GetNearest(test, 1000)))

    Sync()
loop
 
function GetNearest(desired, target)
	if mod(target, desired) = 0 then exitfunction desired
	
	for up = desired to target
		if mod(target, up) = 0 then exit
	next up
	
	for down = desired to 0 step - 1
		if mod(target, down) = 0 then exit
	next down
	
	if abs(desired-up) > abs(desired-down) then exitfunction down
endfunction up

As you can see from the results - the number that is returned is the nearest number to the 'desired' number that will divide into the target

Animation Station - WIP
Happy Flapper
Additional Image Functions (9 sprite slicing etc.)
Additional String Functions
XML read, write, parse
Black theme for Geeny
RGB->HSV->RGB
SpriteSheet XML Control

Back to top

Profile PM Email

easter bunny

12

Years of Service

User Offline

Joined: 20th Nov 2012

Playing: Dota 2

Posted: 20th Feb 2018 13:21 Edited at: 20th Feb 2018 13:22

Link

Mathematically the only way I can think of doing it is to calculate all the divisors of w and see which is closest to d. This page has a fast algorithm for finding the factors (second answer: http://www.quora.com/What-is-an-efficient-algorithm-to-find-divisors-of-any-number

However you can probably get away with a combination of my code and yours. Use mine to approximate the answer, then use brute force to find the real answer. It should provide a slight speed increase (I'm just guessing about that though, maybe it'll even be slower)

Maybe someone smarter than me here can figure out a better way of doing it mathematically, but I certainly can't think of anything.
I suspect there's a way of doing it faster using recursion but I can't figure out how. I just know a lot of work with factors and denominators is done with recursion

My Games - Latest WIP - My Website: Immortal.Digital - FB - Twitter
130,000 installs with AppGameKit and counting

Back to top

Profile PM Email

Scraggle

Moderator

21

Years of Service

User Offline

Joined: 10th Jul 2003

Location: Yorkshire

Posted: 20th Feb 2018 14:06

Link

OK, Thanks for trying Bunny.
I'll probably stick with what I have. It's fast enough for what I need, I just feel dirty using loops when I'm pretty sure there must be a nice simple bit of maths I could be using.

Animation Station - WIP
Happy Flapper
Additional Image Functions (9 sprite slicing etc.)
Additional String Functions
XML read, write, parse
Black theme for Geeny
RGB->HSV->RGB
SpriteSheet XML Control

Back to top

Profile PM Email

Bengismo

7

Years of Service

User Offline

Joined: 20th Nov 2017

Location: Yorkshire, England

Posted: 20th Feb 2018 14:10 Edited at: 20th Feb 2018 19:56

Link

Im at work (where we dont use AppGameKit!) ...so I cant test this but...I think it should work

+ Code Snippet

function GetNearestA(desired, target)
         
    for i = 0 to target
        if mod(target, desired+i) = 0 then exitfunction desired+i
        if mod(target, desired-i) = 0 then exitfunction desired-i
    next i
      
endfunction desired

EDIT - TESTED it - it works as well as your original code scraggle (it should its the same) just looks a bit simpler!

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 20th Feb 2018 14:52

Link

answer = w / round(w / d)

The division in the round function needs to result in a float, so make sure at least d is a float.

Nevermind, I see bunny had the same idea.

Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Back to top

Profile PM Email Website

MadBit

VIP Member

Gold Codemaster

15

Years of Service

User Offline

Joined: 25th Jun 2009

Location: Germany

Posted: 21st Feb 2018 04:35

Link

That's what I got.
It's not much different than what you have, I put it in one loop.
Theoretically, it should be faster.
I don't know if the problem could be solved without a loop.

+ Code Snippet

Function GetNearest(d,w)
	f=w
	for t=0 to w/2
		if mod(w,t) = 0
			t2 = w/t
			if abs(t-d) < abs(f-d) then f = t
			if abs(t2-d) < abs(f-d) then f = t2
		endif
	next
EndFunction

Share your knowledge. It\'s a way to achieve immortality. (Tenzin Gyatso)

Back to top

Profile PM Email

Scraggle

Moderator

21

Years of Service

User Offline

Joined: 10th Jul 2003

Location: Yorkshire

Posted: 21st Feb 2018 15:01

Link

Thanks MadBit.

I can't say whether or not your code works because it causes AppGameKit to crash without error.
I don't know why, I can't see anything that would cause it to crash and yet it does.

Animation Station - WIP
Happy Flapper
Additional Image Functions (9 sprite slicing etc.)
Additional String Functions
XML read, write, parse
Black theme for Geeny
RGB->HSV->RGB
SpriteSheet XML Control

Back to top

Profile PM Email

MadBit

VIP Member

Gold Codemaster

15

Years of Service

User Offline

Joined: 25th Jun 2009

Location: Germany

Posted: 21st Feb 2018 15:12 Edited at: 21st Feb 2018 15:13

Link

sorry it is the for loop. '1 to w' not '0 to w'
and function must return f

Share your knowledge. It\'s a way to achieve immortality. (Tenzin Gyatso)

Back to top

Profile PM Email

baxslash

Valued Member

Bronze Codemaster

17

Years of Service

User Offline

Joined: 26th Dec 2006

Location: Duffield

Posted: 21st Feb 2018 15:40 Edited at: 21st Feb 2018 16:22

Link

This version seems a lot quicker:

+ Code Snippet

function GetNearest2(desired, target)
    d = mod(target, desired)
    for i=0 to d
		if mod(target, desired+i)=0 then exitfunction desired+i
		if mod(target, desired-i)=0 then exitfunction desired-i
	next
endfunction desired

The original averages 1000 runs in 0.016 secs (on my machine) and my version gets around 1000 in 0.0002 secs. You might want to run a few tests yourself on the output but it looks right to me.

EDIT: Test code

test = 500
 
do
	st1# = timer()
	for i=0 to 1000
		if GetPointerPressed()
			test = random(1, 999)
		endif
		GetNearest(test, 1000)
	next
	ft1# = timer()
	time1# = ft1#-ft2#
	
	st2# = timer()
	for i=0 to 1000
		if GetPointerPressed()
			test = random(1, 999)
		endif
		GetNearest2(test, 1000)
	next
	ft2# = timer()
	time2# = ft2#-st2#
	
	Print("original took "+str(time1#) + ", new one took "+str(time2#))
 
    Sync()
loop
  
function GetNearest(desired, target)
    if mod(target, desired) = 0 then exitfunction desired
     
    for up = desired to target
        if mod(target, up) = 0 then exit
    next up
     
    for down = desired to 0 step - 1
        if mod(target, down) = 0 then exit
    next down
     
    if abs(desired-up) > abs(desired-down) then exitfunction down
endfunction up

function GetNearest2(desired, target)
    d = mod(target, desired)
    for i=0 to d
		if mod(target, desired+i)=0 then exitfunction desired+i
		if mod(target, desired-i)=0 then exitfunction desired-i
	next
endfunction desired

+ Code Snippet

test = 500
 
do
	st1# = timer()
	for i=0 to 1000
		if GetPointerPressed()
			test = random(1, 999)
		endif
		GetNearest(test, 1000)
	next
	ft1# = timer()
	time1# = ft1#-ft2#
	
	st2# = timer()
	for i=0 to 1000
		if GetPointerPressed()
			test = random(1, 999)
		endif
		GetNearest2(test, 1000)
	next
	ft2# = timer()
	time2# = ft2#-st2#
	
	Print("original took "+str(time1#) + ", new one took "+str(time2#))
 
    Sync()
loop
  
function GetNearest(desired, target)
    if mod(target, desired) = 0 then exitfunction desired
     
    for up = desired to target
        if mod(target, up) = 0 then exit
    next up
     
    for down = desired to 0 step - 1
        if mod(target, down) = 0 then exit
    next down
     
    if abs(desired-up) > abs(desired-down) then exitfunction down
endfunction up

function GetNearest2(desired, target)
    d = mod(target, desired)
    for i=0 to d
		if mod(target, desired+i)=0 then exitfunction desired+i
		if mod(target, desired-i)=0 then exitfunction desired-i
	next
endfunction desired

EDIT2:
Actually I get incorrect results occasionally. For 166 for example I should get 200. I need to go further than the d value... I will work on it

Using AppGameKit V2 Tier 1

Back to top

Profile PM Email

baxslash

Valued Member

Bronze Codemaster

17

Years of Service

User Offline

Joined: 26th Dec 2006

Location: Duffield

Posted: 21st Feb 2018 16:40

Link

Ok better version:

+ Code Snippet

function GetNearest2(desired, target)
    for i=0 to target
        if mod(target, desired+i)=0 then exitfunction desired+i
        if mod(target, desired-i)=0 then exitfunction desired-i
    next
endfunction desired

I've run this over 30,000 times and got the same results as yours every time. It doesn't seem to run as fast for some reason but it is still quicker.

Using AppGameKit V2 Tier 1

Back to top

Profile PM Email

Bengismo

7

Years of Service

User Offline

Joined: 20th Nov 2017

Location: Yorkshire, England

Posted: 21st Feb 2018 16:41

Link

I posted that exact same function yesterday...lol

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 21st Feb 2018 16:46

Link

Quote: "It doesn't seem to run as fast for some reason but it is still quicker."

Come again? It's not as fast but it's quicker?

Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds

Back to top

Profile PM Email Website

baxslash

Valued Member

Bronze Codemaster

17

Years of Service

User Offline

Joined: 26th Dec 2006

Location: Duffield

Posted: 21st Feb 2018 16:51

Link

Quote: "I posted that exact same function yesterday...lol"

Great minds think alike

I didn't look at everyone else's solutions.

Quote: "Come again? It's not as fast but it's quicker?"

Not as fast as the previous version I posted but quicker than the OP.

Using AppGameKit V2 Tier 1

Back to top

Profile PM Email

Bengismo

7

Years of Service

User Offline

Joined: 20th Nov 2017

Location: Yorkshire, England

Posted: 21st Feb 2018 20:19

Link

Your previous version fails on various numbers , so it doesn't really matter if it was quicker or not.... as it was broken.

The one I posted (then you did as well) works fine.

The function could be put into a plugin for speed and run without the interpreter to make it much quicker. A lookup table would be another good option.

Back to top

Profile PM

baxslash

Valued Member

Bronze Codemaster

17

Years of Service

User Offline

Joined: 26th Dec 2006

Location: Duffield

Posted: 22nd Feb 2018 08:53

Link

Quote: "Your previous version fails on various numbers , so it doesn't really matter if it was quicker or not.... as it was broken."

True, after a little testing I realised it was failing on some numbers because I was going by the remainder of the original number. This only worked about 80% of the time.

Quote: "The function could be put into a plugin for speed and run without the interpreter to make it much quicker. A lookup table would be another good option."

Agreed, I had a quick go at a lookup table version and even in AppGameKit Basic it runs about 500 times faster than the original function. Just run the setup once during initialisation (assuming you will only be checking for one target number), then use "lookup[desired]" to get the answer. Alternatively the version Bengismo came up with first works fine if the target number is likely to change:

+ Code Snippet

global lookup as integer[]
function SetupNearest(target)
	lookup.length = -1
	for i=0 to target
		if i=0
			lookup.insert(0)
		else
			lookup.insert(GetNearest(i, target))
		endif
	next
endfunction

function GetNearest(desired, target)
    for i=0 to target
        if mod(target, desired+i)=0 then exitfunction desired+i
        if mod(target, desired-i)=0 then exitfunction desired-i
    next
endfunction desired

Using AppGameKit V2 Tier 1

Back to top

Profile PM Email

Sorry your browser is not supported!

AppGameKit Classic Chat / Mathamatics help please!