how can i make this faster ??

[ddndd]

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

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 >

[TerranceN]

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.

[ddndd]

ok so i did what u said it kinda helped not much thought so if u have any ideas u can tell me

[TerranceN]

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.

[TheGuardian001]

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.

[Turing_Gamer]

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.

[Euphoracle]

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.

[copthesaint]

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

[Turing_Gamer]

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

[Euphoracle]

lol a copyright message. thats rich.

[chrisbrown]

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.

[Euphoracle]

and thus rsa wins. w00ts =)

[copthesaint]

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)

[chrisbrown]

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.

[Prabhakar Ragde]

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.