Atmel AVR32 UC3L Measured Power
No assertions from me :-) - I don't know enough about this cpu to assert anything. The following is based on experience, the datasheet and a good helping of guestimating. 

Summary: Not enough data BUT


200 +/- 50uA/MHz  + allowance for activated peripherals as per Table 7-6 p46 in datasheet


Copied below.

In your position I'd 


Lean heavily on Atmel.
Do some measurements myself.
Refine the rudimentary method suggested below. 




Interestingly, the total of peripheral currents below sum to about 100 uA/MHz so the core consumption predominates. This suggests 


a minimum of about 150 uA/MHz (a bit less than 165) and 
a maximum of about 360 uA/MHz (based on the two ill defined datasheet examples =  260 + 100 from table).  


I'd not lightly dismiss Fibonacci numbers as a "light load".
A significant portion of the current drain for a CMOS processor comes from charging and discharging capacitive nodes, whether memory bits or port pins or registers or whatever. Anything that causes more bit changes is liable to require more power. I don't know why their division routines is lower powered, but something that "just adds" is potentially able to change as many bits as most things.