Could PIC handle this?

~5000 over the entire UK. distribution varies a little, but not hugely.
indexing it by longitude is probably best.

In message <41be53ef$1_1@omega.dimensional.com>, hamilton 
<hamilton@deminsional.com> writes
>David wrote:
>> Could a PIC handle interfacing via rs232 with a GPS unit, and
>> comparing the location against a list of ~5000 stored positions, and
>> alerting (LED/LCD) if any points are considered close enough (~1-2km,
>> using haversine formula, perhaps)?
>>  I guess the points would have to be stored on a CF/MMC card. They
>> would be updated/changed time to time...
>
>I would be hard pressed to believe that a PIC can do this.
>
>The largest/fastest PIC can do floating point math in seconds.
>
>5000 * 2 floating point calculations (lat/long) would require 10s on 
>thousands of seconds. ( 10,000 seconds / 3600/hr = 2.77 hours )
>
>Let alone storage and retrieval of 5000 pairs (lat/long) numbers.
Check out this month's EPE mag (uk)
http://www.epemag.wimborne.co.uk
They published a device based on a cheapish GPS module with NMEA output 
and a 16F873 that does exactly what the OP requires, they even explain 
the math.
>
>Searching an external flash memory device would take a long time as well.
>
>There are many other low cost solutions that can better handle this 
>problem. If your are cheap and this in not on a schedule, sure have fun.
>
>But, when do you want to see this done ?  Not within a single semester !!
>
>hamilton

-- 
Clint Sharp

"Clint Sharp" <clint@clintsmc.demon.co.uk> wrote

> Check out this month's EPE mag (uk)
> http://www.epemag.wimborne.co.uk
> They published a device based on a cheapish GPS module with NMEA output 
> and a 16F873 that does exactly what the OP requires, they even explain 
> the math.

Ah, neat: you program it when you pass a camera and it beeps when you pass
that way again.

So it has to store information to the resolution of the GPS, but it 
doesn't have to cover the world.

Still wouldn't have picked a PIC.

All the computer software ever written can be executed on a computer
with just one instruction ... 

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
Remove spaces etc. to reply: n o lindan at net com dot com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

David wrote:

> Could a PIC handle interfacing via rs232 with a GPS unit, and
> comparing the location against a list of ~5000 stored positions, and
> alerting (LED/LCD) if any points are considered close enough (~1-2km,
> using haversine formula, perhaps)?
> 
> I guess the points would have to be stored on a CF/MMC card. They
> would be updated/changed time to time...

PICs come pretty big now - up to 128K (18F7820). I have used the 18F452 
and it's nicely capable - fast clocking, hardware multiply, sane stack 
depth, good peripherals. The 128K parts are a lot bigger and a bit better.

That's not to say the PIC is the best beast for the job. I've been 
mostly using MSP430 recently, but they stop at 60K. I suspect that 
beyond this, ARM is the best choice. Certainly plenty of FLASH.

I also suspect that your distance algorithm is a small part of the code, 
both time and space. I would identify the critical part as being the 
database of 5000 locations. How much memory do you need? At 20 bytes 
each (5 single precision floats), you should fit into a 128K part and 
have plenty space for kerfuffle. Perhaps cheaper to use a low 
temperature PIC and slap in a 24512 or three.

Regards,
Mike.

hamilton wrote:
> David wrote:
> 
>> Could a PIC handle interfacing via rs232 with a GPS unit, and
>> comparing the location against a list of ~5000 stored positions, and
>> alerting (LED/LCD) if any points are considered close enough (~1-2km,
>> using haversine formula, perhaps)?
>>
>> I guess the points would have to be stored on a CF/MMC card. They
>> would be updated/changed time to time...
> 
> 
> I would be hard pressed to believe that a PIC can do this.
> 
> The largest/fastest PIC can do floating point math in seconds.
> 
> hamilton

[raspberry sound] Today's PICs have hardware multiply and run at up to 
40MHz. For 8 bitters, they're rather good.

Mike Page wrote:

> David wrote:
> 
>> Could a PIC handle interfacing via rs232 with a GPS unit, and
>> comparing the location against a list of ~5000 stored positions, and
>> alerting (LED/LCD) if any points are considered close enough (~1-2km,
>> using haversine formula, perhaps)?
>> 
>> I guess the points would have to be stored on a CF/MMC card. They
>> would be updated/changed time to time...
> 
> PICs come pretty big now - up to 128K (18F7820). I have used the 18F452
> and it's nicely capable - fast clocking, hardware multiply, sane stack
> depth, good peripherals. The 128K parts are a lot bigger and a bit better.
> 
> That's not to say the PIC is the best beast for the job. I've been
> mostly using MSP430 recently, but they stop at 60K. I suspect that
> beyond this, ARM is the best choice. Certainly plenty of FLASH.
> 
> I also suspect that your distance algorithm is a small part of the code,
> both time and space. I would identify the critical part as being the
> database of 5000 locations. How much memory do you need? At 20 bytes
> each (5 single precision floats), you should fit into a 128K part and
> have plenty space for kerfuffle. Perhaps cheaper to use a low
> temperature PIC and slap in a 24512 or three.
> 
> Regards,
> Mike.

I think you could offload some of the redundant math to database creation 
time. If you drop the idea of floats and went with scaled integers, you 
could speed things up and save a great deal of space.

Scale the GPS into binary integers. There are 360 degrees of longitude, 
each with 60 minutes and 4 places of fractional minutes. So 360 * 60 
* 10,000 = 216e6 or a little less than 2^28 or 28 bits. Latitude would be 
27 bits. This would speed up the math considerably. The only *conversion* 
needed would be the GPS data into the binary format. Each point would be 
8 bytes with no loss of resolution.

As I mentioned before, you could really speed up 'homing-in' on the closest 
location by simply taking the sum of the differences of lon and lat. No 
multiply would be needed. You could then take the time to perform 64-bit 
multiplies on the closest 5 or 10 to select the true, closest item.

BTW, the sum of the differences technique is really pretty efficient. The 
worst case error occurs when the points are at 45 degrees from each other.  
Even then, it's still really close.

Noel

On Tue, 14 Dec 2004 23:37:16 +0000, the renowned Mike Page
<brian@brian.com> wrote:

>hamilton wrote:
>> David wrote:
>> 
>>> Could a PIC handle interfacing via rs232 with a GPS unit, and
>>> comparing the location against a list of ~5000 stored positions, and
>>> alerting (LED/LCD) if any points are considered close enough (~1-2km,
>>> using haversine formula, perhaps)?
>>>
>>> I guess the points would have to be stored on a CF/MMC card. They
>>> would be updated/changed time to time...
>> 
>> 
>> I would be hard pressed to believe that a PIC can do this.
>> 
>> The largest/fastest PIC can do floating point math in seconds.
>> 
>> hamilton
>
>[raspberry sound] Today's PICs have hardware multiply and run at up to 
>40MHz. For 8 bitters, they're rather good.

Some of todays PICs (18x and 17x at least) have sissy 8 x 8 hardware
multiply. The MSP430 has a manly 16 x 16 hardware multiply, which is 4
times the work. Although technically a 16-bit micro, it competes
directly. Also, 40MHz is the oscillator frequency-- the minimum
instruction cycle is 100ns. 


Best regards, 
Spehro Pefhany
-- 
"it's the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

On Tue, 14 Dec 2004 21:58:18 -0500, Spehro Pefhany
<speffSNIP@interlogDOTyou.knowwhat> wrote:

>>[raspberry sound] Today's PICs have hardware multiply and run at up to 
>>40MHz. For 8 bitters, they're rather good.
>
>Some of todays PICs (18x and 17x at least) have sissy 8 x 8 hardware
>multiply. The MSP430 has a manly 16 x 16 hardware multiply, which is 4
>times the work. Although technically a 16-bit micro, it competes
>directly. Also, 40MHz is the oscillator frequency-- the minimum
>instruction cycle is 100ns. 

It is interesting to compare these clock frequencies and minimum cycle
times to the original MC6800 some 30 years ago running at 1 MHz and 1
us. Despite the huge improvement in silicon processing, the
performance of current 8 bitters is only modest. 

While on wider processors, much of the performance increase is due to
using more and more transistors, the maximum clock frequency has also
grown several decades. 

Thus, I would have expected that with current 130 nm line widths, the
performance would have been at least two decades better than with the
original 6800/8080/8085/Z80 processors, even with a similar number of
gates. 

Are manufacturers afraid that fast 8 bitters would reduce the market
for 16/32 bit processors ?

Paul

On Wed, 15 Dec 2004 08:57:17 +0200, the renowned Paul Keinanen
<keinanen@sci.fi> wrote:

>On Tue, 14 Dec 2004 21:58:18 -0500, Spehro Pefhany
><speffSNIP@interlogDOTyou.knowwhat> wrote:
>
>>>[raspberry sound] Today's PICs have hardware multiply and run at up to 
>>>40MHz. For 8 bitters, they're rather good.
>>
>>Some of todays PICs (18x and 17x at least) have sissy 8 x 8 hardware
>>multiply. The MSP430 has a manly 16 x 16 hardware multiply, which is 4
>>times the work. Although technically a 16-bit micro, it competes
>>directly. Also, 40MHz is the oscillator frequency-- the minimum
>>instruction cycle is 100ns. 
>
>It is interesting to compare these clock frequencies and minimum cycle
>times to the original MC6800 some 30 years ago running at 1 MHz and 1
>us. Despite the huge improvement in silicon processing, the
>performance of current 8 bitters is only modest. 
>
>While on wider processors, much of the performance increase is due to
>using more and more transistors, the maximum clock frequency has also
>grown several decades. 
>
>Thus, I would have expected that with current 130 nm line widths, the
>performance would have been at least two decades better than with the
>original 6800/8080/8085/Z80 processors, even with a similar number of
>gates. 
>
>Are manufacturers afraid that fast 8 bitters would reduce the market
>for 16/32 bit processors ?
>
>Paul

I've seen ads (from Western Design Center?) that show that a 65C02
core would run at several hundred MHz if manufactured in a modern
process. Maybe the market price per chip times the demand for such a
fast, but lean, processor won't support the up-front cost of such a
process. 


Best regards, 
Spehro Pefhany
-- 
"it's the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

On Wed, 15 Dec 2004 02:14:59 -0500, Spehro Pefhany
<speffSNIP@interlogDOTyou.knowwhat> wrote:

>I've seen ads (from Western Design Center?) that show that a 65C02
>core would run at several hundred MHz if manufactured in a modern
>process. Maybe the market price per chip times the demand for such a
>fast, but lean, processor won't support the up-front cost of such a
>process. 

The ever popular flash is generally slow and I/O pins generally don't need to be
near that fast, so the external interface is probably what makes this kind of
fast embedded 8-bit CPU in the center not so interesting.  And if you add in
cache and inbound and outbound fifos, etc., it's not so interesting anymore to
have a 65C02 in the middle of all that.  And there's the core voltage versus
what people would like for their applications, perhaps.

Jon