Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Messages - Xeda112358

Pages: 1 ... 41 42 [43] 44 45 ... 317
631
Humour and Jokes / Re: Apparently, 2014 started Monday
« on: December 31, 2013, 11:53:08 pm »
7 minutes left where I am from! I'll be back next year, I guess :P

632
Math and Science / Fermat Factoring (Zeda's Method)
« on: December 31, 2013, 03:45:50 pm »
As some have seen me talking in IRC, I have my own rendition of Fermat factoring. I compared it to what I thought was a typical approach and my method asymptotically replaces a square root operation with a subtract and an increment. In complexity terms:

Square root is on the level of multiplication and division, so O(M(n))
Subtraction is O(n)
Increment, if my calculations are correct, is O(1) (in the case of the algorithm described below, invert bit 1, if that returns 0, invert bit 2, ... to increment by 2)

So while Fermat factoring isn't as efficient as the general number field sieve, the method I have is more efficient than a typical approach to Fermat factoring.

To describe the idea, notice that a2-b2=(a-b)(a+b). This means that, given our number c, if we can find a difference of two squares so that they equal c, then we have a pair of factors for c. For example, 102-52=75, so 75=(10-5)(10+5)=5*15. If c>1 and is a positive odd integer, it will always have a trivial solution (the difference between consecutive squares is 1,3,5,7,..., so this is "trivial"). Any other solutions are non-trivial and imply that c is composite. If only the trivial solution exists, c is prime.
Spoiler For proof:
Assume c is composite. Then c=nm where n,m are natural numbers greater than 1. If we let n be the larger of the two, then we have:
n=(a+b)
m=(a-b)
m+2b=a-b+2b=a+b
m+2b=n
n-m=2b
(n-m)/2=b
n=a+b
n=a+(n-m)/2
n-(n-m)/2=a
(n+m)/2=a
(n-m)/2=b

The trivial solution is (c+1)/2=a,(c-1)/2=b factoring to 1c=c. If c is composite, it has a non trivial solution. Now the other direction, if c is prime, it does not have a non-trivial solution. Essentially, notice that if there is a non trivial solution, where n is not (c+1)/2 and m is not (c-1)/2, then we can factor c as (n-m)(n+m) which is a contradiction.

Summary:
If c is prime, it has only the trivial solution.
If c is composite, it has non-trivial solutions.
The next few steps toward solving this formula are the typical approaches and I do the same thing. We notice that a>sqrt(c).
Spoiler For proof:
Rewrite a2-b2=c as a2-c=b2. Then we see that a2-c is non-negative, so:
a2>=c,
a>=sqrt(c).
So then with our algorithm, we can initialise a=cieling(sqrt(c). That is the smallest that a can be, so now we enter the naive algorithm, checking if the difference a2-c is a perfect square:
Code: [Select]
ceiling(sqrt(c))→a
While notperfectsqaure(a*a-c)
a+1→a
EndWhile
sqrt(a*a-c)→b
Return {a-b,a+b}
However, the next step away from the naive approach is to notice that every time you add 1 to a, the difference increases by 2a+1. So you can save some computations by keeping track of the difference and updating at each iteration:
Code: [Select]
ceiling(sqrt(c))→a
a*a-c→b2
While notperfectsqaure(b2)
b2+2a+1→b2
a+1→a
EndWhile
sqrt(b2)→b
Return {a-b,a+b}
However, that notperfectsquare() routine will likely require computing the square root at least once (twice if done naively). My approach takes the optimisation another step further by keeping track of how far away b2 is from a perfect square. With this, note that if b2 is the next lowest perfect square below a2-c, then the one above is b2+2*b2+1, so if the difference between b and b2 exceeds 2*b2+1, we need to increment b and adjust the difference:
Code: [Select]
ceiling(sqrt(c))→a
a*a-c→diff
floor(sqrt(diff))→b
diff-b*b→diff
While diff>0
  diff+a+a+1→diff
  a+1→a
  While diff>=(2b+1)
    diff-b-b-1→diff
    b+1→b
  EndWhile
EndWhile
Return {a-b,a+b}
As it is, the inner while loop converges to iterating 1 time pretty quickly (bounded the square root of the difference between the initial guess for a and c). We can say then that the original square root required at each iteration is replaced by 1 subtract and 1 increment.

Rewriting this for some more efficiency, we can do:
Code: [Select]
ceiling(sqrt(c))→a
a*a-c→diff
floor(sqrt(diff))→b
diff-b*b→diff
2a+1→a
2b+1→b
While diff>0
  diff+a→diff
  a+2→a
  While diff>=b
    diff-b→diff
    b+2→b
  EndWhile
EndWhile
floor(a/2)→a
floor(b/2)→b
Return {a-b,a+b}
At the chip level, those +2 can also be increments requiring O(1) time instead of additions requiring O(n) time. This means that each iteration of the algorithm requires about:
- 2 add/sub operations
- 2 increments
- 3 compares (that can be changed to simply checking for overflow, so these can be trivially removed)

And the maximum number of iterations are based on how far the actual a value is from the original estimate. If we know C is an odd composite (as, for example, RSAs) then this is a pretty crummy upper bound of c/3-sqrt(c) in the worst case (c=3*p).
Spoiler For Example 1:
So let's try to factor 14111. First, estimate a=119. Then 1192-14111=50, so our initial b is 7, with difference of 1. (50-7^2=1).
a=119, b=7, diff=1. Increment a, add 2*119+1 to diff
a=120, b=7, diff=240. 240>=7*2+1, so increment b, subtract 15 from diff
a=120, b=8, diff=225. increment b, subtract 17 from diff
a=120, b=9, diff=208. increment b, subtract 19 from diff
a=120, b=10, diff=189. increment b, subtract 21 from diff
a=120, b=11, diff=168. increment b, subtract 23 from diff
a=120, b=12, diff=145. increment b, subtract 25 from diff
a=120, b=13, diff=120. increment b, subtract 27 from diff
a=120, b=14, diff=93. increment b, subtract 29 from diff
a=120, b=15, diff=64. increment b, subtract 31 from diff
a=120, b=16, diff=33. increment b, subtract 33 from diff
a=120, b=17, diff=0. diff=0, so we have found a and b

So 14111=(120-17)(120+17)=103*137.
Spoiler For Example 2:
c=75. Then a=9 initially, 81-75=6, so b=2, diff=2
a=9, b=2, diff =2
a=10, b=2, diff =21
a=10, b=3, diff =16
a=10, b=4, diff =9
a=10, b=5, diff =0

So 75=(10-5)(10+5)=5*15.
Spoiler For More Notes:
I came up with this algorithm a few years ago while working on Grammer. This was before Grammer had Line() or Circle() drawing routines, during the summer (when I didn't have internet). Grammer had a Circle() routine long before Line() because the Circle() routine was derived from my Fermat factoring routine above. The routine above can be thought of as interpolating a curve of the form y=sqrt(x^2-b) compared to y=sqrt(z-x^2) where z is the radius squared. However, the algorithm above stops when it lands exactly on a point (when its error=0) whereas circle drawing typically requires the whole curve to be drawn. I believe that my method of drawing circles and lines is like the Bresenham method, so I made a tutorial saying as much. However, I haven't validated that, so I haven't officially released it.
0,1,4,9, Fermat, Bresenham, Circles, and Lines

My circle and line drawing routines takes advantage of overflow (the c flag) to avoid making comparisons. Likewise:
Code: [Select]
If 0==c%2
  Return {2,a/2}
sqrt(c)→a
If floor(a)=a
  Return {a,a}
1+floor(a)→a
a*a-c→diff
floor(sqrt(diff))→b
diff-b*b→diff
2a-1→a
2b-1→b
diff-b→diff
Loop0:
  a+2→a
  diff+a→diff
  if carry_set
Loop1:
    b+2→b
    diff-b→diff
    GOTO Loop1 IF carry_not_set
  GOTO Loop0 IF zero_not_set
a>>1→a
b>>1→b
Return {a-b,a+b}
I should also note that at the assembly level, my integer square root routines typically also returns the difference between the original input and the next smaller perfect square, so that also helps speed things up a little (getting rid of all of the multiplications).

Sorry for the code nested in a spoiler tag :/

633
Official Contest / Re: TI-Concours 2014
« on: December 27, 2013, 03:50:29 pm »
Cool! Also, for some of the English readers, they might mix up " (excepting PCSE)" as " (accepting PCSE)" since a bunch of English speakers mix up accept/except. In this case, the PCSE models are excluded.

I might join, but I don't think I will be able to do well. It is my last semester of college coming up, so I will be very distracted.

634
Art / Re: General purpose art thread
« on: December 27, 2013, 03:19:30 pm »
Juju got me to try drawing Fluttershy. I need a lot of work :P Plus, I am not familiar enough with the character, so I messed up some anatomical stuff.

635
TI-Nspire / Re: nGL - a fast (enough) 3D engine for the nspire
« on: December 26, 2013, 04:53:54 pm »
The way I make snake games, is I have a buffer of coordinates and to increment the snake, I erase the tail, shift the buffer down, and add a new head at a coordinate computed by the direction you are turning.

You *could* do a snake game where the arena is stationary, the snake always moves forward, and can turn left/right/up/down. However, the controls would get very confusing, especially if you turn the snake upside down. Instead, it would be much easier and probably more fun and cool looking if you rotated the arena and kept the snake oriented the same. Of course, you would have to redraw every element of the snake each time, but that looks like it would be trivial with this engine. To visualise, the head would always be centered in the screen, facing away from the camera, looking in the direction the camera is looking. When you turn left/right/up/down, you could use a different sprite for those directions, but still centered. Then, you just change the camera angle. Incrementing the snake would have to be done based on the current view angles, and you would have to increment it with the camera.

You could just call it a dragon and pretend you were riding one and steering it.

636
Portal X / Re: Portal Prelude
« on: December 25, 2013, 12:15:28 pm »
That's actually pretty cool and turned out really well!

637
TI-Nspire / Re: nGL - a fast (enough) 3D engine for the nspire
« on: December 25, 2013, 01:01:37 am »
Wow, this looks fantastic! Are you able to make a 3D snake that is in a cube instead of a plane? The snake could always go in one direction (away from the screen?) and the player just rotates the view of the box in order to steer the snake. Just an idea ^^

638
TI Z80 / Re: Chaos Game
« on: December 24, 2013, 11:15:35 pm »
What LFSR's are you using? I'd be curious to see if there is an LFSR that does work, as LFSR's are pretty fast.
I figured out that I was using the second one incorrectly. The lower bits are not that great to use, but the upper byte or using both actually turns out really well. I started the seed with 1.

Also, I made an update. It will run a little slower now, but it is much more useful offering many more vertex tests without the need to constantly recompile. You can supply your own vertices or have the program generate N vertices for a regular polygon (it uses a sine routine).

639
TI Z80 / Re: Chaos Game
« on: December 24, 2013, 01:18:33 am »
I am working on updating it to allow custom inputs for vertices. It Currently allows input as a real list in the form of {y1,x1,y2,x2,...} or a complex list where each component is {y1+ix1,y2+ix2,...}.

However, for quick testing it will probably be a lot easier to simply pass a number and have the program generate a regular polygon with the given number of vertices. So should I add this? The program is currently small-ish at 210 bytes plus the RNG to test.

Also, I was thinking of having it be able to take input in a string as "nn,filename" where nn is the number of vertices and filename is the variable that has a data stream to directly test.

Thoughts?

640
TI Z80 / Re: YABAV(A)
« on: December 22, 2013, 01:43:54 pm »
I kind of want to play with compression a bit, now. That is some really good compression, by the way. I am not good on the computer side, but I would like to see what I could do with a few frames to test on.

641
TI Z80 / Re: Chaos Game
« on: December 20, 2013, 11:44:42 pm »
The Mandelbrot set is not a chaos game, actually. A chaos game is just starting with a handful of vertices, and jumping halfway to a randomly selected vertex. Ideally, you would do this for infinitely many points, but we can't, so we just do it for a gazillion.

642
HP Calculators / Re: A clock
« on: December 20, 2013, 02:26:06 pm »
Hi Handmixer! I don't have an HP calc, so I can't test it, but somebody pointed out to me that your codeblock wasn't rendering nicely. Google Chrome users have noticed that nesting code blocks inside of spoilers doesn't work well. If you wanted, I could modify your post to exclude the spoiler tags, or you could by selecting "modify" on your post.

Anyways, thanks for sharing! I know we have a group of HP Prime programmers around here that might be interested in seeing the code!

643
TI Z80 / Re: Chaos Game
« on: December 19, 2013, 12:08:48 pm »
These from CaDan as offered by Geekboy:
Code: [Select]
;  From CaDan, by Iambian and Geekboy
LFSR:
    ld    hl,lfsrseed1
    ld    a,(hl)
    rrca
    ld    (hl),a
    ret    nc
    xor    %00111000
    ld    (hl),a
 ret

;  From CaDan, by Iambian and Geekboy
LFSR2Byte:
  ld hl,(lfsrseed2)
  ld a,L
  rlca
  xor h
  rlca  ;
  rlca  ;
  xor h ;
  rlca
  xor h
  rlca
  adc hl,hl
  ld (lfsrseed2),hl
  ld a,h     ;for combatability
  ret

644
CaDan SHMUP / Re: Cadan v2 - Progress Thread
« on: December 19, 2013, 09:51:27 am »
I seem to forget to post on things I think are cool :P This is really awesome work! The speed of these routines is ridiculous.
nanami <3 (we miss you TsukasaZX)
Where has Tsukasa gone? I feel like I missed what happened :/

645
TI Z80 / Re: Chaos Game
« on: December 19, 2013, 09:36:57 am »
Ohhhh, Nice visualisation. That could end up in a neat screensaver!
Allow me to point you to my avatar... It is actually the same fractal, but with a coloring scheme and you can see it all at once (the calculator screen was too small) :)

Also, I tested the Ion random routine as well as a few more LCGs and they turned out to work well. The LCGs only worked nicely because I did mod_65521 and mod_65519 instead of mod_65536. I also made it so that the user can press [CLEAR] to exit instead of just [ON] and I made it update every drawn pixel instead of every 256 by interleaving LCD updating into the pixel plotting routine. It is actually faster this way, taking ~8000 extra t-states for every 256 pixels instead of using that extremely slow OS routine at about 150000 (or was it 300 000?).

Anyways, in order of the best randomness routines currently included:

rand== 1 is fairly chaotic (it passes many tests showing small amounts of bias) and it is very fast. This is the LFSR that Cadan is currently using. (Use the upper byte)

rand == 3 is one I wrote. If I remember correctly, it is the method used by the calculators called l'Écuyer's algorithm. It basically runs two LCGs at the same time, then it multiplies the two using another modulo operation producing an output. This is also called an MLCG (Multiple Linear Congruential Generator) I believe. As reference, the OS routine takes more than 170 000 t-states, compared to this routine which takes less than 1600.

rand== 6 is one of the LCGs used in the previous one and also passes both tests. It is also a lot faster on its own, so while it has a much smaller period of 65521, this should be more than enough for games while providing a decent 8-bit RNG.

rand== 4 is the ION routine. If you have ever played an ION game that has 'random' events (like Donkey Kong), you might notice it gets into loops where it starts doing the same things over and over. An easy fix is to press a button. What happens is that the ION routine relies on the R register which gets incremented as code is executed. If there is no input into the system, it falls into predictable behavior because it is the same code executing every time. If you disturb the system with input, such as a keypress that causes a deviation in the game loop, the r register will start behaving more chaotically. In my tests, it worked just fine, though, almost filling in the square.

rand== 5 Is the other LCG that performed slightly worse than the ION routine

rand== 2 Is the 8-bit MCLG which leaves close to 1/4 of the square unfilled (estimate, not actually counted).

rand== 0 is an LFSR which is fast but fails most of the chaos tests. This may be a seeding issue.

EDIT: I was incorrectly testing Cadan's 2-byte LFSR. It is quite excellent.

Pages: 1 ... 41 42 [43] 44 45 ... 317