Computer Science Canada

how can i make this faster ??
Author:  ddndd [ Thu Feb 04, 2010 4:07 pm ]
Post subject:  how can i make this faster ??
What is it you are trying to achieve?
im trying to make turing go faster when it is looking for the factors any ideas ??

Describe what you have tried to solve this problem
delay (-5) i know it is stupid but that was the only thing that came to me Razz

Please specify what version of Turing you are using
<4.1>


Post any relevant code (You may choose to attach the file instead of posting the code if it is too long)

Turing:


<View.Set ("graphics:max;max")
procedure sss
var numb : int
var numb1 : int := 0
var choice : string (1)
var countt :int := 0
loop
put "enter any number"
get numb
put "the factors for your number are:"
loop
%delay (-10000)
    exit when numb1 = numb
    numb1 += 1
    if numb div numb1 = numb / numb1 then
        put numb div numb1 : 15 ..
    end if
end loop
put skip
put "and the first 10 multiples of your number are :"
numb1 := 0
loop
countt := countt + 1
    numb1 += 1
    put countt :5,": ", numb * numb1
    exit when numb1 = 10
end loop
put "again ? y/n"
getch (choice)
if choice = "n" or choice = "N" then
exit
end if
numb1 := 0
cls
end loop
end sss
sss
>

Author:  TerranceN [ Thu Feb 04, 2010 4:52 pm ]
Post subject:  Re: how can i make this faster ??
First, limit the number of times the loop has to go around. (Hint: you never have to go past the square root of the number when you are checking for factors, also, this is the most significant one)

Second, use for loops because you know how many times to go around the loop.

Third, use (numb mod numb1 = 0) instead of (numb div numb1 = numb / numb1). It doesn't really make a noticible difference, but at least its more concise.

Hope that helps.
Author:  ddndd [ Thu Feb 04, 2010 7:50 pm ]
Post subject:  Re: how can i make this faster ??
ok so i did what u said it kinda helped not much thought so if u have any ideas u can tell me
Author:  TerranceN [ Thu Feb 04, 2010 9:23 pm ]
Post subject:  RE:how can i make this faster ??
Well I'm sorry, but when I did those steps I mentioned, it processed finds factors substantially faster.

Perhaps you are limiting the number of loops incorrectly.

Consider that every factor has a corresponding factor, therefore if we also find the corresponding factor when we find a factor, we only have to go up to the square root. For example, 144, factors are

1
2
3
4
6
8
9
12
16
18
24
36
48
72
144

but if you also find the corresponding factor when you find each factor, you will only find unique factors up until the square root of the number

1 and 144
2 and 72
3 and 48
4 and 36
6 and 24
8 and 18
9 and 16
12 and 12

therefore using corresponding factors, we only had to go up to 12 instead of 144 in order to get all the factors. This effect just increases as numbers get higher, which would make a substantial difference in performance.

I hope I said that right, and I hope that makes it more clear about what I meant.
Author:  TheGuardian001 [ Thu Feb 04, 2010 10:06 pm ]
Post subject:  Re: how can i make this faster ??
Yeah, if implemented correctly, TerranceN's solution will optimize it pretty much as far as you can possibly get...

For example, with the original program, all factors of 34525432 were found in a bit over 48.3 seconds.
With the changes he suggested, all factors were found in about 4 milliseconds.
Author:  Turing_Gamer [ Fri Feb 05, 2010 8:30 am ]
Post subject:  Re: how can i make this faster ??
You can't rush the loops, it takes time for it to run through the loop until it is finished.
Depending on the size of the number, the time it takes to do that will take longer.
I made a prime and a prime-printing program and it had that delay but there is little you can do.
Author:  Euphoracle [ Fri Feb 05, 2010 8:55 am ]
Post subject:  RE:how can i make this faster ??
There is no efficient way to factor large numbers. If you figure this out, you've beaten RSA and you'll get a doctorate from a good number of schools.
Author:  copthesaint [ Fri Feb 05, 2010 11:58 am ]
Post subject:  Re: how can i make this faster ??
Well One way is to use mod ()

for example:

Turing:
var num : int
get num
put "Factors: "
for i : 1 .. num
    if num mod i = 0 then
        put i
    end if
end for


This would speed up the process for finding Factors
Author:  Turing_Gamer [ Fri Feb 05, 2010 12:56 pm ]
Post subject:  Re: how can i make this faster ??
In that case, me > RSA
Here are the programs.

If you enter a large number, you will notice it take longer than usual.
No way of stopping this.

COPYRIGHT: 2009
Author:  Euphoracle [ Fri Feb 05, 2010 1:34 pm ]
Post subject:  RE:how can i make this faster ??
lol a copyright message. thats rich.
Author:  chrisbrown [ Fri Feb 05, 2010 3:51 pm ]
Post subject:  RE:how can i make this faster ??
Ah but cop, when num has say ~600 digits, checking 10^300 possibilities one by one isn't going to find you an answer in a reasonable amount of time (i.e. before humans are extinct), hence the need for an efficient process.
Author:  Euphoracle [ Fri Feb 05, 2010 4:21 pm ]
Post subject:  RE:how can i make this faster ??
and thus rsa wins. w00ts =)
Author:  copthesaint [ Sat Feb 06, 2010 2:35 am ]
Post subject:  Re: RE:how can i make this faster ??
methodoxx @ Fri Feb 05, 2010 wrote:
Ah but cop, when num has say ~600 digits, checking 10^300 possibilities one by one isn't going to find you an answer in a reasonable amount of time (i.e. before humans are extinct), hence the need for an efficient process.


no point, unless you want to make a long number system. Turings max int value is 2147483647 and if you really think people will use factors such as which, then just make a program that tells you if a number is a factor of another. Ex//

Turing:
var x,y : int
put "number: "..
get x
put "has a factor of: "..
get y
put "= ", (x mod (y) = 0)



Author:  chrisbrown [ Sat Feb 06, 2010 11:42 am ]
Post subject:  Re: RE:how can i make this faster ??
I think we're talking about a P vs NP problem here. It's easy to check if a number x has a factor of y. The problem arises when trying to find all factors of x.

Also,
copthesaint @ Sat Feb 06, 2010 2:35 am wrote:
if you really think people will use factors such as which

Take a look at RSA cryptography, where security increases with larger keys. A key of 2 billion and change is tiny compared to the numbers actually used. Just because Turing can't handle larger numbers doesn't mean they aren't used.
Author:  Prabhakar Ragde [ Sat Feb 06, 2010 12:42 pm ]
Post subject:  Re: RE:how can i make this faster ??
methodoxx @ Sat Feb 06, 2010 11:42 am wrote:
I think we're talking about a P vs NP problem here. It's easy to check if a number x has a factor of y. The problem arises when trying to find all factors of x.


When classifying problems using complexity classes like P and NP, it is customary to cast them as "decision problems", ones with yes/no answers. The decision version is: given n and m, does n have a nontrivial factor less than m? (If you can solve this, you can easily find a factor using binary search.)

This problem is not known to be NP-complete, or believed to be, since it is in both NP and co-NP (there is succinct "evidence" for both yes and no answers). But it is still believed to be "hard", i.e. not in P.

The program with the "only up to the square root" modification runs in time n^0.5 times little stuff. The best known factorization algorithms run in time n^0.333 times little stuff. So there is not a lot of improvement to be had here. Note that the size of the input is log n, so these are exponential-time algorithms.

On the other hand, you can squeeze some constant factors out. For example, don't try even divisors greater than 2.
Author:  copthesaint [ Sun Feb 07, 2010 6:33 pm ]
Post subject:  RE:how can i make this faster ??
Seriously, methodoxx, quit acting like such a retard, If you look up I gave him a method that will get him ALL factors of x, also No freakin person is every going to use this program for finding factors (Sorry ddndd). Also Make sure you read my WHOLE post next time, ok? I SAID

"...if you really think people will use factors such as which, then just make a program that tells you if a number is a factor of another."

Quit freakin Croping my sentences.
I DIDNT SAY THEY WERNT USED, OMG, WHERE DO YOU SEE THAT? :/ some people on the internet.

Read what the topic title is: How can I make this faster? Enough said.

Edit:
Sorry for language, just a bit ticked, Also just because I said you *acting like a retard, It doesnt mean I really think you are.
Author:  chrisbrown [ Sun Feb 07, 2010 7:38 pm ]
Post subject:  RE:how can i make this faster ??
I have to apologize here, I thought you were responding to Euphoracle's post right above yours, not to the OP's. I didn't mean to offend, I guess I was having a completely different discussion.
Author:  copthesaint [ Mon Feb 08, 2010 1:19 am ]
Post subject:  RE:how can i make this faster ??
all good Smile so anyways, we may have ruined this thread lol... Sorry ddndd lol
Author:  Turing_Gamer [ Mon Feb 08, 2010 8:29 am ]
Post subject:  Re: how can i make this faster ??
And I thought I had it I am disgusted , but then again that would be too easy for the RSA to figure out. Oh well Hit Wall
Author:  ddndd [ Wed Feb 10, 2010 6:34 pm ]
Post subject:  Re: how can i make this faster ??
i finally did it Razz
it is much faster now and i used the idea that someone said so i dont take any credit for making it faster but here it is
what do u guys thinks ??
Author:  TerranceN [ Wed Feb 10, 2010 7:51 pm ]
Post subject:  Re: how can i make this faster ??
What is the point of this line

Turing:
exit when count > sqrt (numb) - 1 and count < sqrt (numb) + 1 or numb div count > sqrt (numb) - 1 and numb div count < sqrt (numb) + 1


when you already have a for loop that should go up to the sqrt of the number. Just change '1 .. numb' to '1 .. round(sqrt(numb))' and remove the exit when line.


Also, what does this do?

Turing:
if countlast = numb div count or numblast = count then
    exit
end if
numblast := numb div count
countlast := count


What you wrote will work, but there is a lot of unneeded code. You should try adding comments to your code in order to figure out what is and isn't needed.
Author:  ddndd [ Wed Feb 10, 2010 8:00 pm ]
Post subject:  Re: how can i make this faster ??
TerranceN @ Wed Feb 10, 2010 7:51 pm wrote:
What is the point of this line

Turing:
exit when count > sqrt (numb) - 1 and count < sqrt (numb) + 1 or numb div count > sqrt (numb) - 1 and numb div count < sqrt (numb) + 1


when you already have a for loop that should go up to the sqrt of the number. Just change '1 .. numb' to '1 .. round(sqrt(numb))' and remove the exit when line.


Also, what does this do?

Turing:
if countlast = numb div count or numblast = count then
    exit
end if
numblast := numb div count
countlast := count


What you wrote will work, but there is a lot of unneeded code. You should try adding comments to your code in order to figure out what is and isn't needed.



lol ya i know i have a lot of extra stuff cuz i was just trying different things for it to work, i guess i forgot to remove the extra stuff so i just need to take out a couple of stuff ...
Author:  USEC_OFFICER [ Wed Feb 10, 2010 9:02 pm ]
Post subject:  RE:how can i make this faster ??
Wait, you have a line which really is just asking if count = sqrt (numb) twice. Also or statements don't work that way.
Author:  ddndd [ Wed Feb 10, 2010 10:29 pm ]
Post subject:  Re: RE:how can i make this faster ??
USEC_OFFICER @ Wed Feb 10, 2010 9:02 pm wrote:
Wait, you have a line which really is just asking if count = sqrt (numb) twice. Also or statements don't work that way.


k i just said that i was trying to make it work so i did different things im going to change it
Author:  USEC_OFFICER [ Thu Feb 11, 2010 12:59 pm ]
Post subject:  RE:how can i make this faster ??
Well I somehow posted that before I saw your other post, so I'm sorry. *Goes into corner and sobs*
Author:  Turing_Gamer [ Thu Feb 11, 2010 1:02 pm ]
Post subject:  Re: how can i make this faster ??
You should be ashamed of yourself for hurting a dear old gramp here...*Walks to USEC_OFFICER*
There, there it's alright. I agree with you...
Very Happy
Author:  ddndd [ Thu Feb 11, 2010 4:31 pm ]
Post subject:  Re: how can i make this faster ??
k here u go guys this is an updated version with comments and everything although the comments arent that great cuz i really hate making comments but i think it is simple enough to understand if u have any questions u can ask Very Happy
Author:  TerranceN [ Thu Feb 11, 2010 7:57 pm ]
Post subject:  RE:how can i make this faster ??
[numb] [numb div count]
1 144
2 72
3 48
4 36
6 24
8 18
9 16
12 12

Notice we got all the factors by just going up to the square root of numb. So why does your for loop still go up to numb?

If you still don't understand how a for loop is supposed to work, read the tutorial here.
Author:  ddndd [ Fri Feb 12, 2010 3:10 pm ]
Post subject:  Re: RE:how can i make this faster ??
TerranceN @ Thu Feb 11, 2010 7:57 pm wrote:
[numb] [numb div count]
1 144
2 72
3 48
4 36
6 24
8 18
9 16
12 12

Notice we got all the factors by just going up to the square root of numb. So why does your for loop still go up to numb?

If you still don't understand how a for loop is supposed to work, read the tutorial here.


cuz if you put for count : 1.. sqrt (numb)
there would be a error, the reason for that is the square root of the number might have a decimal and that is not allowed in a for loop ... so dont u think that i know what a for loop is ??
Author:  TheGuardian001 [ Fri Feb 12, 2010 3:12 pm ]
Post subject:  Re: how can i make this faster ??
ddndd wrote:

cuz if you put for count : 1.. sqrt (numb)
there would be a error, the reason for that is the square root of the number might have a decimal and that is not allowed in a for loop ...


Which is where the beauty of the round command comes in.
Author:  USEC_OFFICER [ Fri Feb 12, 2010 4:28 pm ]
Post subject:  RE:how can i make this faster ??
Ah, the round command. *Teary eyed* It's so beatiful. Until turing turns ints into floats, by itself (Which C++ does, I believe) the round command is your friend. If you're ever making a game that uses trig, make all your varibles float and then round. That way it's more accurate. Just saying. (Saying what? About how great round is.)(Still can't spell)
Author:  ddndd [ Fri Feb 12, 2010 6:17 pm ]
Post subject:  Re: how can i make this faster ??
nope that is ok i dont want to change it, i like it my way ...

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy