Comments (1)
Given the following implementation of exponentiation functions:
// Raise a number to a power.
/// * `base` - The number to raise.
/// * `exp` - The exponent.
/// # Returns
/// * `felt252` - The result of base raised to the power of exp.
fn pow_u256(base: felt252, exp: felt252) -> felt252 {
if exp == 0 {
return 1;
} else {
return base * pow_u256(base, exp - 1);
}
}
fn fast_pow(mut base: u256, exponent: u256) -> u256 {
let mut result = 1;
let mut exp = exponent;
loop {
if exp == 0 {
break;
};
if (exp % 2) == 1 {
result *= base;
}
base *= base;
exp /= 2;
};
result
}
Here are the gas usage of each function to compute 2**32
❯ scarb test -f test_fast_pow
Running tests for package: kakarot
testing kakarot ...
running 1 tests
[DEBUG] (raw: 0x7b82c
test kakarot::tests::test_utils::test_helpers::test_fast_pow ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 63 filtered out;
❯ scarb test -f test_pow
Running tests for package: kakarot
testing kakarot ...
running 1 tests
[DEBUG] (raw: 0x13088
Fast exponentiation makes less sense in Cairo then regular exponentiation - because
- Bitshifting is not available yet (and even if it was, it would probably be an expensive operation
- Division is an expensive operation
Therefore, I think we should not use fast exponentiation algorithms.
from kakarot-ssj.
Related Issues (20)
- dev: make `memory_expansion_cost` return the new memory size
- bug: `memory_expansion_cost` function doesn't calculate new memory size after expansion properly
- dev: move Account storage inside Account model
- feat: use sha256 syscall HOT 5
- feat: add RIP-7212 to the list of precompiles Cairo1Helpers module HOT 1
- feat: migrate to starknet-foundry HOT 2
- feat: merge EOA and Contract Accounts
- feat: account upgradeability mechanism
- dev: update edition to 2023_11 HOT 4
- refactor: move `valid_jumpdests` in the `Message` struct HOT 1
- feat: create Starknet backend
- refactor: merge EOA and ContractAccount model
- feat: add extra constructor arguments to Kakarot
- refactor: delete contract_account module
- refactor: remove account types
- refactor: rename storage variables
- refactor: change Kakarot interface to CairoZero's
- epic: investigate test-runner possibilities
- feat: mark accounts created in a transaction as "created"
- feat: pad p256verify input to 160 bytes HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from kakarot-ssj.